//code by p1ckle/sft/yukicoder //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") #include #define int long long int #define F first #define X first #define S second #define Y second #define mid ((start+end)/2) #define all(x) x.begin(), x.end() #define ub(a, b) upper_bound(all(a), b) #define lb(a, b) lower_bound(all(a), b) #define pb push_back #define endl '\n' using namespace std; typedef vector vi; typedef pair pii; typedef vector> vpii; typedef long double ld; const int inf = 1e18, mod = 1e9+7; vpii dr4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, dr8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}}; bool ccw(pii a, pii b, pii x) { return ((a.X*b.Y + b.X*x.Y + x.X*a.Y) - (a.Y*b.X + b.Y*x.X + x.Y*a.X) >= 0); } bool cw(pii a, pii b, pii x) { return ((a.X*b.Y + b.X*x.Y + x.X*a.Y) - (a.Y*b.X + b.Y*x.X + x.Y*a.X) <= 0); } int dis(pii a, pii b) { return (b.F-a.F)*(b.F-a.F)+(b.S-a.S)*(b.S-a.S); } int n, t, x[30003], y[30003], dx[30003], dy[30003], ans = inf; vpii vp, uh, lh, hul; int a, b; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> t; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> dx[i] >> dy[i]; int l = 0, r = t; while (r - l >= 3) { int m[2] = {(l*2+r)/3, (l+r*2+2)/3}, tmp[2] = {0, 0}; for (int k = 0; k < 2; k++) { vp.clear(); uh.clear(); lh.clear(); hul.clear(); for (int i = 1; i <= n; i++) vp.pb({x[i]+m[k]*dx[i], y[i]+m[k]*dy[i]}); sort(all(vp)); uh.pb(vp[0]); uh.pb(vp[1]); for (int i = 2; i < n; i++) { if (uh.size() >= 2 && ccw(uh[uh.size()-2], uh[uh.size()-1], vp[i])) uh.pop_back(); uh.pb(vp[i]); } lh.pb(vp[0]); lh.pb(vp[1]); for (int i = 2; i < n; i++) { if (lh.size() >= 2 && cw(lh[lh.size()-2], lh[lh.size()-1], vp[i])) lh.pop_back(); lh.pb(vp[i]); } hul = uh; for (int i = lh.size()-2; i >= 0; i--) hul.pb(lh[i]); int nh = hul.size()-1; int p1 = 0, p2 = 1; for (; p1 < nh; p1++) { while (!ccw(hul[p1], hul[p1+1], {hul[p1].F+(hul[p2+1].F-hul[p2].F), hul[p1].S+(hul[p2+1].S-hul[p2].S)})) p2 = (p2+1)%nh; tmp[k] = max(tmp[k], dis(hul[p1], hul[p2])); } } //cout << l << ' ' << r << ' ' << tmp[0] << ' ' << tmp[1] << endl; if (tmp[0] > tmp[1]) l = m[0]; else r = m[1]; } //cout << l << ' ' << r << endl; for (int k = l; k <= r; k++) { int tmp = 0; vp.clear(); uh.clear(); lh.clear(); hul.clear(); for (int i = 1; i <= n; i++) vp.pb({x[i]+k*dx[i], y[i]+k*dy[i]}); sort(all(vp)); uh.pb(vp[0]); uh.pb(vp[1]); for (int i = 2; i < n; i++) { if (uh.size() >= 2 && ccw(uh[uh.size()-2], uh[uh.size()-1], vp[i])) uh.pop_back(); uh.pb(vp[i]); } lh.pb(vp[0]); lh.pb(vp[1]); for (int i = 2; i < n; i++) { if (lh.size() >= 2 && cw(lh[lh.size()-2], lh[lh.size()-1], vp[i])) lh.pop_back(); lh.pb(vp[i]); } hul = uh; for (int i = lh.size()-2; i >= 0; i--) hul.pb(lh[i]); int nh = hul.size()-1; int p1 = 0, p2 = 1; for (; p1 < nh; p1++) { while (!ccw(hul[p1], hul[p1+1], {hul[p1].F+(hul[p2+1].F-hul[p2].F), hul[p1].S+(hul[p2+1].S-hul[p2].S)})) p2 = (p2+1)%nh; tmp = max(tmp, dis(hul[p1], hul[p2])); } if (tmp < ans) { ans = tmp; l = k; } } cout << l << endl << ans; }

제출 #80673

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: