Submission #37945

#TimeUsernameProblemLanguageResultExecution timeMemory
37945patrikpavic2SIR (COI15_sir)C++14
0 / 100
336 ms17644 KiB
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <set> #include <map> #include <cmath> #define mp make_pair #define X first #define Y second using namespace std; typedef long long llint; typedef pair < llint,llint> pii; const llint N = 1e5 + 500; const llint INF = 0x3f3f3f3f; const llint MOD = 1e9 + 7; vector < pii > hull; vector < pii > v2; vector < pii > hull2; pii P; llint n,m,nn; llint ccw(pii A,pii B,pii C){ return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y); } llint dis(pii A,pii B){ return (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y); } bool cmp(pii A,pii B){ if(ccw(A,B,P) == 0) return dis(A,P) < dis(B,P); return ccw(P,A,B) > 0; } bool cmpa(pii a, pii b) { if(a.second != b.second) return a.second < b.second; return a.first < b.first; } void convex_hull(){ sort(v2.begin(),v2.end(), cmpa); P = v2[0]; sort(v2.begin() + 1,v2.end(),cmp); hull2.push_back(P); for(int i = 1;i<v2.size();i++){ while(hull2.size() >= 2 && ccw(hull2[hull2.size()-2],hull2[hull2.size()-1],v2[i]) <= 0){ hull2.pop_back(); } hull2.push_back(v2[i]); } nn = hull2.size(); } llint solve(){ llint sol = 0; llint cur = 0; int j = 0,k = 0; for(int i = 0;i<n;i++){ while(nn > 1 && ccw(hull[i],hull2[k],hull2[(k+1)%nn]) <= 0){ k=(k+1)%nn; } if(i == j) j = (j + 1) % n; while(ccw(hull[i],hull[j],hull2[k]) > 0){ cur += abs(ccw(hull[i],hull[(j-1+n)%n],hull[j])); j=(j+1)%n; } sol = max(sol, cur); if(i != j && i + 1 != j) cur -= abs(ccw(hull[i],hull[(i+1)%n],hull[(j-1+n)%n])); if(i == j) j = (j + 1) % n; } return sol; } void load(){ scanf("%lld",&n); for(llint i = 0;i<n;i++){ llint x,y;scanf("%lld%lld",&x,&y); hull.push_back(make_pair(x,y)); } scanf("%lld",&m); for(llint i = 0;i<m;i++){ llint x,y;scanf("%lld%lld",&x,&y); v2.push_back(make_pair(x,y)); } } int main(){ load(); convex_hull(); printf("%lld\n",solve()); }

Compilation message (stderr)

sir.cpp: In function 'void convex_hull()':
sir.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1;i<v2.size();i++){
                    ^
sir.cpp: In function 'void load()':
sir.cpp:82:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
                     ^
sir.cpp:84:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         llint x,y;scanf("%lld%lld",&x,&y);
                                          ^
sir.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&m);
                     ^
sir.cpp:89:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         llint x,y;scanf("%lld%lld",&x,&y);
                                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...