[BOJ] #10255:교차점

풀이

CCW에 대해서 공부했다!!! 

뭐 이런식으로

아

이따가

해야지

 

Code

#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct point { int x, y; };
int CCW(point a, point b, point c) {
	int tmp = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
	if (tmp > 0) return 1;
	else if (tmp < 0)return -1;
	else return 0;
}
bool chk(int st, int en, int d, int u) {
	if (u > st && d < st)return true;
	if (u > en && d < en)return true;
	if (u <= en && d >= st)return true;
	if (u >= en && d <= st)return true;
	return false;
}
bool intersect(point p1, point p2, point p3, point p4) {
	if (CCW(p1, p2, p3) == CCW(p1, p2, p4))return false;
	if (CCW(p3, p4, p1) == CCW(p3, p4, p2))return false;
	return true;
}
bool diagonal(point p1, point l1, point l2) {
	if ((l2.x - l1.x)*(p1.y - l1.y) == (l2.y - l1.y)*(p1.x - l1.x))return true;
	return false;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		point mini, maxi, po1, po2;
		scanf("%d %d %d %d", &mini.x, &mini.y, &maxi.x, &maxi.y);
		scanf("%d %d %d %d", &po1.x, &po1.y, &po2.x, &po2.y);
		bool flag = false;
		if (po1.x == po2.x) {
			if (chk(mini.y, maxi.y, min(po1.y, po2.y), max(po1.y, po2.y))) {
				if (po1.x == mini.x || po1.x == maxi.x) {
					printf("4\n");
					flag = true;
				}
			}
			else if (mini.y == po1.y || mini.y == po2.y || maxi.y == po1.y || maxi.y == po2.y) {
				printf("1\n");
				flag = true;
			}
		}
		else if (po1.y == po2.y) {
			if (chk(mini.x, maxi.x, min(po1.x, po2.x), max(po1.x, po2.x))) {
				if (po1.y == mini.y || po1.y == maxi.y) {
					printf("4\n");
					flag = true;
				}
			}
			else if (maxi.x == po1.x || mini.x == po2.x || maxi.x == po1.x || maxi.x == po2.x) {
				printf("1\n");
				flag = true;
			}
		
		}
		if (!flag) {
			int cnt = 0;
			if (intersect({ mini.x,mini.y }, { mini.x,maxi.y }, po1, po2)) {
				if (!diagonal({ mini.x,mini.y }, po1, po2))cnt++;
			}
			if (intersect({ mini.x, mini.y }, { maxi.x,mini.y }, po1, po2)) {
				if (!diagonal({ maxi.x,mini.y }, po1, po2))cnt++;
			}
			//printf("%d\n", cnt);
			if (intersect({ mini.x,maxi.y }, { maxi.x,maxi.y }, po1, po2)) {
				if (!diagonal({ mini.x,maxi.y }, po1, po2))cnt++;
			}
			if (intersect({ maxi.x,mini.y }, { maxi.x,maxi.y }, po1, po2)) {
				if (!diagonal({ maxi.x,maxi.y }, po1, po2))cnt++;
			}
			printf("%d\n", cnt);
		}
	}
}