#include #include #include #define MAX 200000 typedef struct { int x, y; } Point; typedef Point Vector; Point p[MAX]; Point p0; double dist(Point a, Point b) { return hypot(a.x - b.x, a.y - b.y); } Vector p2v(Point from, Point to) { return (Vector){to.x - from.x, to.y - from.y}; } long long cross(Vector a, Vector b) { return (long long)a.x * b.y - (long long)a.y * b.x; } int ccw(Point a, Point b, Point c) { return cross(p2v(a, b), p2v(a, c)) > 0; } double max(double x, double y) { return (x > y) ? x : y; } int angle_cmp(const void *a, const void *b) { Point pa = *(Point *)a; Point pb = *(Point *)b; if (cross(p2v(p0, pa), p2v(p0, pb)) == 0) { double da = dist(p0, pa); double db = dist(p0, pb); return (da > db) - (da < db); } double aa = atan2(pa.y - p0.y, pa.x - p0.x); double ab = atan2(pb.y - p0.y, pb.x - p0.x); return (aa > ab) - (aa < ab); } int find_max(Point *s, Point p, int l, int r) { if (l == r) return l; if (l + 1 == r) return dist(p, s[l]) > dist(p, s[r]) ? l : r; double s1 = dist(p, s[l]); double s2 = dist(p, s[l + 1]); double e1 = dist(p, s[r - 1]); double e2 = dist(p, s[r]); if (s1 < s2 && e1 < e2) { return r; } if (s1 > s2 && e1 > e2) { return l; } int m = (l + r) >> 1; int i1 = find_max(s, p, l, m); int i2 = find_max(s, p, m + 1, r); if (dist(p, s[i1]) > dist(p, s[i2])) { return i1; } else { return i2; } } int main() { int _t; scanf("%d", &_t); while (_t--) { int n; scanf("%d", &n); int min_i = 0, min_y = __INT_MAX__, max_x = ~__INT_MAX__; for (int i = 0; i < n; i++) { scanf("%d %d", &p[i].x, &p[i].y); if (p[i].y < min_y || p[i].y == min_y && p[i].x > max_x) { min_y = p[i].y; max_x = p[i].x; min_i = i; } } if (n == 2) { printf("%d %d %d %d\n", p[0].x, p[0].y, p[1].x, p[1].y); continue; } Point t = p[0]; p[0] = p[min_i]; p[min_i] = t; p0 = p[0]; qsort(p + 1, n - 1, sizeof(p[0]), angle_cmp); Point stack[2 * n + 2]; int top = 0; stack[top++] = p[n - 1]; stack[top++] = p[0]; stack[top++] = p[1]; int i = 2; while (i < n) { if (ccw(stack[top - 2], stack[top - 1], p[i])) stack[top++] = p[i++]; else top--; } Point *s; top--; if (ccw(stack[top - 1], stack[0], stack[1])) { s = stack; } else { top--; s = &stack[1]; } for (int i = 0; i < top; i++) { s[i + top] = s[i]; } int max_u, max_v; double max_dist = 0, d; for (int i = 0; i < top; i++) { int idx = find_max(s, s[i], i + 1, i + top - 1); d = dist(s[i], s[idx]); if (d > max_dist) { max_dist = d; max_u = i; max_v = idx; } } printf("%d %d %d %d\n", s[max_u].x, s[max_u].y, s[max_v].x, s[max_v].y); } return 0; }

제출 #178282

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

체커 출력: