#include #include #include #include #include using namespace std; typedef long long Long; struct Vector2 { Long X; Long Y; }; struct Star { Vector2 Position; Vector2 Velocity; }; static inline Long CounterClockWise(const Vector2& p1, const Vector2& p2, const Vector2& p3) { return (p2.X - p1.X) * (p3.Y - p1.Y) - (p3.X - p1.X) * (p2.Y - p1.Y); } static inline Long ContectedCounterClockWise(const Vector2& p1, const Vector2& p2, const Vector2& p3, const Vector2& p4) { return CounterClockWise({ p1.X + (p3.X - p2.X), p1.Y + (p3.Y - p2.Y) }, p3, p4); } static inline Long SqrDistance(const Vector2& p1, const Vector2& p2) { Long dx = p1.X - p2.X; Long dy = p1.Y - p2.Y; return dx * dx + dy * dy; } vector MaxSqrDistances; static inline Long MaxSqrDistance(const vector& stars, int time) { if (MaxSqrDistances[time] != -1) { return MaxSqrDistances[time]; } vector currentStars(stars.size()); for (int i = 0; i < stars.size(); i++) { currentStars[i] = { stars[i]->Position.X + stars[i]->Velocity.X * time, stars[i]->Position.Y + stars[i]->Velocity.Y * time }; } int startPositionIndex = 0; Vector2 startPosition = { LLONG_MAX, LLONG_MAX }; for (int i = 0; i < currentStars.size(); i++) { Vector2 star = currentStars[i]; if (star.Y > startPosition.Y) continue; if (star.Y == startPosition.Y) { if (star.X > startPosition.X) continue; } startPositionIndex = i; startPosition = star; } swap(currentStars[0], currentStars[startPositionIndex]); sort(currentStars.begin(), currentStars.end(), [&](Vector2 left, Vector2 right) { Long counterClockWise = CounterClockWise(startPosition, left, right); if (counterClockWise == 0LL) { return SqrDistance(startPosition, left) < SqrDistance(startPosition, right); } return counterClockWise > 0LL; }); vector convexHull = { currentStars[0], currentStars[1] }; for (int i = 2; i < currentStars.size(); i++) { while (true) { if (convexHull.size() <= 2) break; Long counterClockWise = CounterClockWise( convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], currentStars[i] ); if (counterClockWise > 0LL) break; convexHull.pop_back(); } convexHull.push_back(currentStars[i]); } if (convexHull.size() == 2) { MaxSqrDistances[time] = SqrDistance(convexHull[0], convexHull[1]); return MaxSqrDistances[time]; } int caliperTop = 1; Long maxDistance = 0; for (int caliperFloor = 0; caliperFloor < convexHull.size(); caliperFloor++) { int nextFloor = (caliperFloor + 1) % convexHull.size(); while (true) { int nextTop = (caliperTop + 1) % convexHull.size(); Long counterClockWise = ContectedCounterClockWise( convexHull[caliperFloor], convexHull[nextFloor], convexHull[caliperTop], convexHull[nextTop] ); if (counterClockWise > 0) { caliperTop = nextTop; } else { break; } } Long distance = SqrDistance(convexHull[caliperFloor], convexHull[caliperTop]); if (distance > maxDistance) maxDistance = distance; } MaxSqrDistances[time] = maxDistance; return maxDistance; } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int starCount; cin >> starCount; int maxTime; cin >> maxTime; vector stars(starCount); MaxSqrDistances = vector(maxTime + 1, -1); for (int i = 0; i < starCount; i++) { Star* input = new Star; cin >> input->Position.X >> input->Position.Y >> input->Velocity.X >> input->Velocity.Y; stars[i] = input; } int startTime = 0; int endTime = maxTime; while (endTime - startTime >= 3) { int midLeftTime = ceil((2 * startTime + endTime) / 3.); int midRightTime = ceil((2 * endTime + startTime) / 3.); Long resultLeft = MaxSqrDistance(stars, midLeftTime); Long resultRight = MaxSqrDistance(stars, midRightTime); if (resultLeft <= resultRight) endTime = midRightTime; else startTime = midLeftTime; } int minimumTime = 0; Long minimumDistance = LLONG_MAX; for (int i = startTime; i <= endTime; i++) { Long distance = MaxSqrDistance(stars, i); if (minimumDistance > distance) { minimumDistance = distance; minimumTime = i; } } cout << minimumTime << "\n" << minimumDistance; }

제출 #90126

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: