레야몬

1. 문제 n개의 도시를 가진 나라가 있다. 이 나라의 도시 중 가장 먼 두 도시를 찾아 그 도시의 좌표를 구하라. 단 모든 도시는 한 평면 위에 있다. -1- 테스트 케이스의 수 T --1- 도시의 개수 \(n(2 \leq n \leq 200,000)\) --n개- x좌표 y좌표 \((-10,000,000 \leq, x, y \leq 10,000,000) x, y \in \mathbb{Z} \) 어떤 수 도시가 같은 점 위에 있는 경우는 없다. 테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다. 2. 재정의 좌표평면에서 가장 먼 두 점의 위치를 구하시오 3. 해결 방법 Convex Hull Algorithm으로 볼록 껍질을 구한다. 임의의 두 점의 거리를 최장거리로 가정하자 두 벡터의 외적으로 캘리퍼..

#include #include #include #define LOOP(i, N) for(int i=1; i> N; LOOP(i, N) { int x, y; cin >> x >> y; p[i] = VEC(x, y); } } bool compare(const VEC &a, const VEC &b) { if(1LL*a.q*b.p != 1LL*a.p*b.q) return 1LL*a.q*b.p < 1LL*a.p*b.q; if(a.y!=b.y) return a.y < b.y; return a.x < b.x; } ll CCW(VEC &a, VEC &b, VEC &c) { return 1LL*(a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y); } int mai..