# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
37935 | patrikpavic2 | SIR (COI15_sir) | C++14 | 309 ms | 18404 KiB |
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;
}
void convex_hull(){
if(v2.size() < 3) {hull2 = v2;return;}
int j = 0;
for(int i = 0;i<v2.size();i++){
if(v2[i].Y < v2[j].Y || (v2[i].Y == v2[i].Y && v2[i].X > v2[i].X))
j = i;
}
swap(v2[0],v2[j]);
P = v2[0];
sort(v2.begin() + 1,v2.end(),cmp);
hull2.push_back(P);
hull2.push_back(v2[1]);
hull2.push_back(v2[2]);
nn = 3;
for(int i = 3;i<m;i++){
while(nn >= 3 && ccw(hull2[nn-2],hull2[nn-1],v2[i]) < 0){
hull2.pop_back();
nn = hull2.size();
}
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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |