제출 #363738

#제출 시각아이디문제언어결과실행 시간메모리
363738arnold518SIR (COI15_sir)C++14
12 / 100
235 ms21116 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 3e5; struct Point { ll x, y; }; Point operator + (Point p, Point q) { return {p.x+q.x, p.y+q.y}; } Point operator - (Point p, Point q) { return {p.x-q.x, p.y-q.y}; } ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; } ll dot(Point p, Point q) { return p.x*q.x+p.y*q.y; } int N, M; Point A[MAXN+10], B[MAXN+10]; vector<Point> UH, DH, CH; bool f(Point p, Point q) { Point d=q-p; if(ccw(q-p, DH[0]-p)<=0) return false; if(ccw(q-p, UH[0]-p)<=0) return false; int lo=-1, hi=DH.size()-2; while(lo+1<hi) { int mid=lo+hi>>1; if(ccw(d, DH[mid+1]-DH[mid])>=0) hi=mid; else lo=mid; } if(ccw(q-p, DH[hi]-p)<=0) return false; lo=-1, hi=UH.size()-2; while(lo+1<hi) { int mid=lo+hi>>1; if(ccw(d, UH[mid+1]-UH[mid])>=0) hi=mid; else lo=mid; } if(ccw(q-p, UH[hi]-p)<=0) return false; return true; } ll ans=0, sum[MAXN+10]; int main() { scanf("%d", &N); for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y); scanf("%d", &M); for(int i=1; i<=M; i++) scanf("%lld%lld", &B[i].x, &B[i].y); sort(B+1, B+M+1, [&](const Point &p, const Point &q) { if(p.x!=q.x) return p.x<q.x; return p.y<q.y; }); for(int i=1; i<=M; i++) { while(DH.size()>1 && ccw(DH[DH.size()-1]-DH[DH.size()-2], B[i]-DH[DH.size()-2])<=0) DH.pop_back(); DH.push_back(B[i]); } reverse(B+1, B+M+1); for(int i=1; i<=M; i++) { while(UH.size()>1 && ccw(UH[UH.size()-1]-UH[UH.size()-2], B[i]-UH[UH.size()-2])<=0) UH.pop_back(); UH.push_back(B[i]); } for(int i=0; i<DH.size(); i++) CH.push_back(DH[i]); for(int i=1; i+1<UH.size(); i++) CH.push_back(UH[i]); for(int i=2; i<=N; i++) { sum[i]=sum[i-1]+ccw(A[i-1], A[i]); } for(int i=1, j=2; i<=N; i++) { for(; i==j || f(A[i], A[j]); j=(j==N ? 1 : j+1)); int t=j-1; if(t==0) t=N; ll val=0; if(i<=t) { val+=sum[t]-sum[i]; } else { val+=sum[N]-sum[i]+sum[t]+ccw(A[N], A[1]); } val+=ccw(A[t], A[i]); val=abs(val); ans=max(ans, val); } printf("%lld\n", ans); }

컴파일 시 표준 에러 (stderr) 메시지

sir.cpp: In function 'bool f(Point, Point)':
sir.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int mid=lo+hi>>1;
      |           ~~^~~
sir.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid=lo+hi>>1;
      |           ~~^~~
sir.cpp: In function 'int main()':
sir.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0; i<DH.size(); i++) CH.push_back(DH[i]);
      |               ~^~~~~~~~~~
sir.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=1; i+1<UH.size(); i++) CH.push_back(UH[i]);
      |               ~~~^~~~~~~~~~
sir.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
sir.cpp:57:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
sir.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  for(int i=1; i<=M; i++) scanf("%lld%lld", &B[i].x, &B[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...