Submission #552112

#TimeUsernameProblemLanguageResultExecution timeMemory
552112patrikpavic2SIR (COI15_sir)C++17
61 / 100
205 ms20064 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()); 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(ccw(hull[i],hull2[k],hull2[(k+1)%nn]) < 0){ k=(k+1)%nn; } while(ccw(hull[i],hull[j],hull2[k]) > 0 || i == j){ cur += ccw(hull[i],hull[(j-1+n)%n],hull[j]); j=(j+1)%n; } sol = max(sol, cur); cur -= ccw(hull[i],hull[(i+1)%n],hull[(j-1+n)%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 of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
sir.cpp: In function 'void load()':
sir.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
sir.cpp:80:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         llint x,y;scanf("%lld%lld",&x,&y);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
sir.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%lld",&m);
      |     ~~~~~^~~~~~~~~~~
sir.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         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...