HDOJ 계산 직선의 교점 수 1466

직선 의 교점 수 를 계산 하 다
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8389    Accepted Submission(s): 3772
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
   
   
   
   

 
Author
lcy
 
Source
ACM 여름 캠프 연습 경기 (9)
 
Recommend
lcy   |   We have carefully selected several similar problems for you:   1176  1087  1003  1159  1058 
직선
n = 1 시     교점 n = 2 시     교점 n = 3 시     교점 n = 4 시  1. 제4 조 와 나머지 직선 은 모두 평행 = > 교점 이 없다.2. 제4 조 는 그 중의 두 개 와 평행 하고 교점 수 는 (n - 1) * 1 + 0 = 3 이다.3. 네 번 째 줄 은 그 중의 한 줄 과 평행 이다. 이 두 평행 직선 과 다른 두 점 의 교점 수 는 (n - 2) * 2 = 4 이 고 다른 두 직선 은 평행 일 수도 있 고 교차 할 수도 있 기 때문에 교점 수 는 (n - 2) * 2 + 0 = 4 또는 (n - 2) * 2 + 1 = 5 4, 네 번 째 직선 은 그 어떠한 직선 과 평행 하지 않 고 교점 수 는 (n - 3) * 3 + 0 = 3 또는 (n - 3) * 3 + 2 = 5 또는 (n - 3) * 3 + 3 = 6 즉 n = 4 일 때 이다.0 개, 3 개, 4 개, 5 개, 6 개의 서로 다른 교점 이 있다.   
n = 4 의 경우 평행선 의 수 를 차례로 줄인다.n 개의 직선 이 있다 고 가정 하면 이 n 개의 직선 의 교점 수 는 (n - i) * i 와 j 의 합 으로 볼 수 있다. 여기 (n - i) 는 평행선 의 줄 수 를 나타 내 고 i 는 자유 선의 줄 수 를 나타 내 며 j 는 i 개의 자유 선의 교점 수 를 나타 낸다.1 개의 자유 선과 (n - i) 의 평행선 은 반드시 (n - i) * 1 개의 교점 이 있 기 때문에 여기 서 자유 선과 평행선 이 평행 하지 않 는 다 고 밝 혔 다. 그렇지 않 으 면 자유 선과 평행선 은 구분 할 필요 가 없다.그러면 i 개의 자유 선과 평행선 의 교점 총 수 는 (n - i) * i 이다. i 개의 자유 선 은 서로 평행 할 수도 있 고 교차 할 수도 있 기 때문에 i 개의 자유 선 자체 의 교점 수 j 를 더 해 야 한다.

#include<stdio.h>
int p[21][200];
int main()
{
	int i,j,k;
	for(i=1;i<21;i++)
	p[i][0]=1;
	for(k=2;k<21;k++)
	 for(i=1;i<k;i++)
	  for(j=0;j<200;j++)
	   if(p[i][j])//  i   j          。 
	   p[k][j+(k-i)*i]=1;//k-i    ，i    。 
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		int x=(n-1)*n/2;
		printf("0");
		for(i=1;i<=x;i++)
		if(p[n][i])
		printf(" %d",i);
	    printf("
");
	}
	return 0;
}