Submission #37939

#TimeUsernameProblemLanguageResultExecution timeMemory
37939patrikpavic2SIR (COI15_sir)C++14
0 / 100
319 ms21980 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,hull3; 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(A.Y == B.Y) return A.X < B.X; return A.Y < B.Y; } void convex_hull(){ sort(v2.begin(),v2.end(),cmp); for(int i = 0;i<v2.size();i++){ pii x = v2[i]; while(hull2.size() >= 2 && ccw(hull2[hull2.size() - 1],hull2[hull2.size()-2],x) >= 0) hull2.pop_back(); hull2.push_back(x); } hull2.pop_back(); hull3 = hull2; hull2.clear(); for(int i = 0;i<v2.size();i++){ pii x = v2[i]; while(hull2.size() >= 2 && ccw(hull2[hull2.size()-1], hull2[hull2.size() - 2],x) <= 0) hull2.pop_back(); hull2.push_back(x); } for(int i = 0;i<hull2.size();i++) hull3.push_back(hull2[hull2.size() - i - 1]); hull2 = hull3; hull2.pop_back(); } 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:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v2.size();i++){
                    ^
sir.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v2.size();i++){
                    ^
sir.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<hull2.size();i++)
                    ^
sir.cpp: In function 'void load()':
sir.cpp:86:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
                     ^
sir.cpp:88: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:91:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&m);
                     ^
sir.cpp:93: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...