#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF __INT_MAX__ #define endl '\n' #define PLL pair #define X first #define Y second #define MAX (200'000 + 1) #define MAX_LEVEL (int)floor(log2(MAX)) PLL operator-(PLL p2, PLL p1) { return {p2.X - p1.X, p2.Y - p1.Y}; } long long getDist(PLL p1, PLL p2); long long CCW(PLL p1, PLL p2, PLL p3); bool cmpMinY(PLL p1, PLL p2); bool cmpCCW(PLL p1, PLL p2); void makeConvexHull(void); int TC, N; vector points, convex_hull; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> TC; while (TC--) { points.clear(), convex_hull.clear(); cin >> N; for (int i = 1; i <= N; i++) { int x, y; cin >> x >> y; points.push_back({x, y}); } makeConvexHull(); PLL ans1, ans2; long long max_dist = 0; for (int i_cur = 0, j_cur = 1; i_cur < convex_hull.size(); i_cur++) { int i_next = (i_cur + 1) % convex_hull.size(); while (true) { int j_next = (j_cur + 1) % convex_hull.size(); if (CCW({0, 0}, convex_hull[i_next] - convex_hull[i_cur], convex_hull[j_next] - convex_hull[j_cur]) > 0) j_cur = j_next; else break; } long long dist = getDist(convex_hull[i_cur], convex_hull[j_cur]); if (dist > max_dist) { max_dist = dist; ans1 = convex_hull[i_cur]; ans2 = convex_hull[j_cur]; } } cout << ans1.X << " " << ans1.Y << " " << ans2.X << " " << ans2.Y << endl; } return 0; } long long getDist(PLL p1, PLL p2) { return pow((p2.X - p1.X), 2) + pow((p2.Y - p1.Y), 2); } long long CCW(PLL p1, PLL p2, PLL p3) { return (p1.X * p2.Y + p2.X * p3.Y + p3.X * p1.Y) - (p1.Y * p2.X + p2.Y * p3.X + p3.Y * p1.X); } bool cmpMinY(PLL p1, PLL p2) { if (p1.Y == p2.Y) return p1.X < p2.X; return p1.Y < p2.Y; } bool cmpCCW(PLL p1, PLL p2) { long long ccw = CCW(points[0], p1, p2); if (ccw != 0) return ccw > 0; if (p1.Y == p2.Y) return p1.X < p2.X; return p1.Y < p2.Y; } void makeConvexHull(void) { sort(points.begin(), points.end(), cmpMinY); sort(points.begin() + 1, points.end(), cmpCCW); convex_hull.push_back(points[0]); convex_hull.push_back(points[1]); for (int i = 2; i < N; i++) { while (convex_hull.size() >= 2) { PLL point2 = convex_hull.back(); convex_hull.pop_back(); PLL point1 = convex_hull.back(); if (CCW(point1, point2, points[i]) > 0) { convex_hull.push_back(point2); break; } } convex_hull.push_back(points[i]); } }

제출 #10319

제출 정보

제출 결과

제출 코드

찾은 반례