Submission #153213

#TimeUsernameProblemLanguageResultExecution timeMemory
153213gs18103먼 별 (KOI16_dist)C++14
2 / 100
198 ms2412 KiB
#include <bits/stdc++.h> #define x first #define y second #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair <ll, ll> pll; ll arr[30303][4]; pll base; int n, T; ll ccw(pll a, pll b, pll c) { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } ll dis(pll a, pll b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } ll cal_dis(int t) { vector <pll> p, ch; for(int i = 0; i < n; i++) { p.emplace_back(arr[i][0] + arr[i][2] * (ll)t, arr[i][1] + arr[i][3] * (ll)t); } sort(all(p)); //p.erase(unique(all(p)), p.end()); base = p[0]; sort(p.begin(), p.end(), [](pll a, pll b) { return ccw(base, a, b) > 0; }); ch.push_back(base); for(int i = 1; i < n; i++) { while(ch.size() >= 2) { pll p1 = ch[ch.size()-2], p2 = ch[ch.size()-1]; if(ccw(p1, p2, p[i]) > 0) break; ch.pop_back(); } if(p[i] != base) ch.push_back(p[i]); } int idx = 0; ll ret = 0; for(int i = 0; i < ch.size(); i++) { for(int j = 0; j < ch.size(); j++) { ret = max(ret, dis(ch[i], ch[j])); } } return ret; } int search(int s, int e) { if(s + 10 >= e) { ll dis = 9000000000000000000LL; for(int i = s; i <= e; i++) { dis = min(dis, cal_dis(i)); } for(int i = s; i <= e; i++) { if(dis == cal_dis(i)) return i; } } int t1 = (2 * s + e) / 3, t2 = (s + 2 * e) / 3; ll dis1 = cal_dis(t1), dis2 = cal_dis(t2); if(dis1 <= dis2) return search(s, t2); else return search(t1, e); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> T; for(int i = 0; i < n; i++) { for(int j = 0; j < 4; j++) { cin >> arr[i][j]; } } int ans = search(0, T); cout << ans << '\n' << cal_dis(ans); }

Compilation message (stderr)

dist.cpp: In function 'll cal_dis(int)':
dist.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ch.size(); i++) {
                 ~~^~~~~~~~~~~
dist.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ch.size(); j++) {
                  ~~^~~~~~~~~~~
dist.cpp:43:6: warning: unused variable 'idx' [-Wunused-variable]
  int idx = 0;
      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...