This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |