Submission #554059

#TimeUsernameProblemLanguageResultExecution timeMemory
554059MardukSIR (COI15_sir)C++14
0 / 100
1055 ms21112 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN = (3e5+7), INF = (1e9+7); struct pt{ ll x,y; }; int n,m; float sol; vector<pt> points; vector<pt> ch; vector<pt> pol; pt d1 = {INF,INF}, P0 = {INF,INF};; int distSq(pt P1, pt P2){ return (P1.x-P2.x)*(P1.x-P2.x) + (P1.y-P2.y)*(P1.y-P2.y); } int ccw(pt P1, pt P2, pt P3){ if(((P3.x-P1.x)*(P2.y-P1.y) - (P3.y-P1.y)*(P2.x-P1.x)) == 0) return 0; return (((P3.x-P1.x)*(P2.y-P1.y) - (P3.y-P1.y)*(P2.x-P1.x)) > 0)? -1:1; } bool cmp(pt P1, pt P2){ if(ccw(P0,P1,P2) == 0) return distSq(P0,P1) < distSq(P0,P2); return ccw(P0,P1,P2)+1; } float area(pt P1, pt P2, pt P3){ if(ccw(P1,P2,P3) == 0) return 0; float a = sqrt(distSq(P1,P2)); float b = sqrt(distSq(P2,P3)); float c = sqrt(distSq(P3,P1)); float s = (a+b+c)/2; return sqrt(s*(s-a)*(s-b)*(s-c)); } int main(){ cin >> n; for(int i = 0;i<n;i++){ int x,y; cin >> x >> y; if(y < d1.y || (y == d1.y && x < d1.x)) d1 = {x,y}; pol.push_back({x,y}); } cin >> m; for(int i = 0;i<m;i++){ int x,y; cin >> x >> y; if(y < P0.y || (y == P0.y && x < P0.x)) P0 = {x,y}; points.push_back({x,y}); } sort(points.begin(), points.end(), cmp); ch.push_back(points[0]); ch.push_back(points[1]); for(int i = 2;i<points.size();i++){ while(ccw(ch[ch.size()-2], ch[ch.size()-1], points[i])<=0) ch.pop_back(); ch.push_back(points[i]); } P0 = d1; sort(pol.begin(), pol.end(), cmp); // cout << "paprike\n"; // for(pt P : ch) cout << P.x << ' ' << P.y << "\n"; // cout << "\n\n\n"; int t = 0; for(int i = 0;i<n;i++){ while(!(ccw(pol[i],ch[(t-1+ch.size())%ch.size()],ch[t]) < 0 && ccw(pol[i],ch[t],ch[(t+1)%ch.size()]) >= 0)) t = (t+1)%ch.size(); // cout << pol[i].x << ' ' << pol[i].y << " <-> " << ch[t].x << ' ' << ch[t].y << "\n"; int d = (i+1)%n; float A = 0; while(ccw(pol[i],pol[d],ch[t])>0) { // cout << pol[d].x << ' ' << pol[d].y << " -> " << ccw(pol[i],pol[d],ch[t]) << "\n"; // cout << "A+=" << area(pol[i],pol[d],pol[(d-1+n)%n]) << " = " << A+area(pol[i],pol[d],pol[(d-1+n)%n]) << "\n"; // cout << "P( " << pol[i].x << ' ' << pol[i].y << " ," << pol[d].x << ' ' << pol[d].y << " ," << pol[(d-1+n)%n].x << ' ' << pol[(d-1+n)%n].y << " )\n"; A+=area(pol[i],pol[d],pol[(d-1+n)%n]); d=(d+1)%n; } d = (d-1+n)%n; // cout << "OMG " << pol[d].x << ' ' << pol[d].y << "\n\n"; sol = max(sol,A); } cout << sol*2; return 0; }

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 2;i<points.size();i++){
      |                   ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...