hdoj_1466 직선 의 교점 수 를 계산 하 다

직선 의 교점 수 를 계산 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6625    Accepted Submission(s): 2921
Problem Description
평면 에 n 개의 직선 이 있 고 3 선의 공통점 이 없 으 며 이 직선 들 이 몇 가지 서로 다른 교점 이 있 는 지 물 어보 세 요.
예 를 들 어 n = 2 이면 가능 한 교점 수량 은 0 (평행) 또는 1 (평행 하지 않 음) 이다.
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 테스트 인 스 턴 스 는 한 줄 을 차지 하 며 각 줄 은 하나의 정수 n (n < 20) 을 포함 하고 n 은 직선 수량 을 표시 합 니 다.
 
Output
모든 테스트 인 스 턴 스 는 한 줄 의 출력 에 대응 하고 작은 것 부터 큰 것 까지 모든 교차 방안 을 보 여 줍 니 다. 그 중에서 모든 수 는 가능 한 교차 포인트 이 고 모든 줄 의 정수 사 이 를 빈 칸 으로 구분 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    2
3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0 1
0 2 3
   
   
   
   

1. 제4 조 와 나머지 직선 은 모두 평행 = > 0 + 4 * 0 + 0 = 0;2. 제4 조 는 그 중의 두 개 와 평행 하고 교점 수 는 0 + (n - 1) * 1 + 0 = 3 이다.
3. 네 번 째 조 는 그 중의 한 줄 과 평행 이다. 이 두 줄 의 평행 직선 과 다른 두 줄 의 교점 수 는 (n - 2) * 2 = 4 이 고 다른 두 줄 의 직선 은 평행 일 수도 있 고 교차 할 수도 있 기 때문에 교점 수 는 다음 과 같다.
    0+（n-2）*2+0=4    혹은 0+(n-2)*2+1=5     
4. 네 번 째 직선 은 그 어떠한 직선 과 평행 하지 않 고 교점 수 는 다음 과 같다.
    0+(n-3)*3+0=3  또는 0 + (n - 3) * 3 + 2 = 5 또는 0 + (n - 3) * 3 + 3 = 6
즉 n = 4 시 에는 0 개, 3 개, 4 개, 5 개, 6 개의 서로 다른 교점 이 있다.
상기 n = 4 의 분석 과정 에서 우 리 는 m 개의 직선 교점 방안 수 = (m - r) 개의 평행선 과 r 개의 직선 이 교차 하 는 교점 수 를 발견 했다. + r 조 직선 자체 의 교점 방안 = (m - r) * r + r 조 간 자체 의 교점 방안 수 (0 < = r < m)

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 21

int main()
{
	freopen("in.txt", "r", stdin);
	int n, i, j, k, x;
	vector<int>array[MAX];
	array[1].push_back(0);
	array[2].push_back(0);
	array[2].push_back(1);
	for(i = 3; i < MAX; i++) // i   
	{
		for(j = 0; j < i; j++)
		{
			if(j == 0)
			{
				array[i].push_back(0);
			}
			else
			{
				for(k = 0; k < array[j].size(); k++)
				{
					array[i].push_back((i - j) * j + array[j][k]);
				}
			}
		}
		sort(array[i].begin(), array[i].end());
	}
	while(cin >> n)
	{
		x = array[n][0];
		cout << x << " ";
		for(i = 1; i < array[n].size() - 1; i++)
		{
			if(x != array[n][i])
			cout << array[n][i] << " ";
			x = array[n][i];
		}
		if(x != array[n][array[n].size() - 1])
		cout << array[n][i] << endl;
	}
	return 0;
}