Submission #105078

#TimeUsernameProblemLanguageResultExecution timeMemory
105078ShtefSIR (COI15_sir)C++14
0 / 100
1049 ms16696 KiB
#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; typedef long long ll; typedef pair <ll, ll> pll; #define x first #define y second #define mp make_pair int n, m; pll a[300005], b[300005]; vector <pll> gore, dolje, h; int ccw(pll x, pll y, pll z){ ll ret = x.x * (y.y - z.y) + y.x * (z.y - x.y) + z.x * (x.y - y.y); if(ret > 0) return 1; if(ret < 0) return -1; return 0; } void initconvexhull(){ sort(b, b + m); gore.push_back(b[0]); dolje.push_back(b[0]); for(int i = 1 ; i < m ; ++i){ if(i == m - 1 || ccw(b[0], b[i], b[m - 1]) < 0){ while((int)gore.size() >= 2 && ccw(gore[(int)gore.size() - 2], gore.back(), b[i]) > 0){ gore.pop_back(); } gore.push_back(b[i]); } } for(int i = 1 ; i < m ; ++i){ if(i == m - 1 || ccw(b[0], b[i], b[m - 1]) > 0){ while((int)dolje.size() >= 2 && ccw(dolje[(int)dolje.size() - 2], dolje.back(), b[i]) < 0){ dolje.pop_back(); } dolje.push_back(b[i]); } } for(int i = 0 ; i < (int)dolje.size() ; ++i){ h.push_back(dolje[i]); } for(int i = (int)gore.size() - 2 ; i > 0 ; --i){ h.push_back(gore[i]); } } ll povrsina(vector <pll> pts){ ll ret = 0; for(int i = 0 ; i < (int)pts.size() ; ++i){ ret += (pts[i].x * pts[(i + 1) % ((int)pts.size())].y - pts[(i + 1) % ((int)pts.size())].x * pts[i].y); } return ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0 ; i < n ; ++i){ cin >> a[i].x >> a[i].y; } cin >> m; for(int i = 0 ; i < m ; ++i){ cin >> b[i].x >> b[i].y; } initconvexhull(); m = (int) h.size(); int l = 1, r = 1; int hl = (int)dolje.size() - 1, hr = 0; ll sol = 0; for(int i = 0 ; i < n ; ++i){ while(ccw(a[i], h[hl], h[(hl + 1) % m]) > 0){ hl = (hl + 1) % m; } while(ccw(a[i], h[hr], h[(hr + 1) % m]) < 0){ hr = (hr + 1) % n; } if(i == l) l = (l + 1) % n; if(i == r) r = (r + 1) % n; while(ccw(a[i], h[hl], a[l]) <= 0){ l = (l + 1) % n; } while(ccw(a[i], h[hr], a[r]) < 0){ r = (r + 1) % n; } r = (r - 1 + n) % n; vector <pll> v; for(int j = l ; j != i ; j = (j + 1) % n){ v.push_back(a[j]); } v.push_back(a[i]); sol = max(sol, povrsina(v)); v.clear(); for(int j = i ; j != r ; j = (j + 1) % n){ v.push_back(a[j]); } v.push_back(a[r]); sol = max(sol, povrsina(v)); v.clear(); } cout << sol << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...