c언어 2358번 평행선 (백준)

#include <stdio.h>
#include <stdlib.h>

int cmp(const void*a, const void*b) {return(*(int*)a-*(int*)b);}

int main() {
	int n,i,x,y=0,z;
	scanf("%d",&n);
	int a[n],b[n];
	for(i=0;i<n;i++) scanf("%d %d",&a[i],&b[i]);
	qsort(a,n,4,cmp);
	qsort(b,n,4,cmp);
	
	for(z=1,x=a[0],i=1;i<n;i++) if(z && x==a[i]) {++y;z=0;} else if(x!=a[i]) {z=1;x=a[i];}
	for(z=1,x=b[0],i=1;i<n;i++) if(z && x==b[i]) {++y;z=0;} else if(x!=b[i]) {z=1;x=b[i];}
	printf("%d",y);
}

 

풀이 : 정렬

 

0. x좌표 값과, y좌표 값을 각각 다른 배열에 저장합니다.

1. 오름차순으로 정렬을 합니다.

2. 같은 좌표가 연속적으로 2번나온다면, 두 점을 지나며 x 또는 y 축에 평행한 선 1개가 있음을 알 수 있습니다. (같은 좌표가 3개이상이더라도, 직선은 1개이므로 그 이후에 중복되는 값은 무시하면 됩니다)

3. 직선의 개수를 출력합니다.

 

위 코드에서 z의 역할

1 1 1 ... 이런 식으로 같은 좌표가 연속적으로 3개 이상이 되면 z 가 없는 경우, (1,1) (1,1) 이렇게 연속적으로 2번인 것이 2번 나오므로 직선이 2개가 있다고 잘못 판단합니다. 이를 방지하기위해서 존재합니다.

z 가 0 일 때의 의미는, "이미 이 좌표에 대한 직선이 있음을 구했으니 그 뒤로 같은 좌표가 오더라도 무시" 입니다.

z 가 1 일 때의 의미는, "아직 특정 좌표에 대한 연속적인 값이 오지 않음"입니다.