QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357570 | #5111. Take On Meme | InfinityNS | RE | 0ms | 0kb | C++14 | 3.4kb | 2024-03-19 00:01:39 | 2024-03-19 00:01:41 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a,pt b){return tie(a.x,a.y)<tie(b.x,b.y);}
bool operator == (pt a,pt b){return tie(a.x,a.y)==tie(b.x,b.y);}
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ll dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ll sq(pt a){return dot(a,a);}
vector<pt> ConvexHull(vector<pt> a){
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
if(a.size()<=1)return a;
vector<pt> hull;
int sz=0;
for(int t=0;t<2;t++){
int was=sz;
for(pt p:a){
while(sz>was+1 && cross(p-hull[sz-2],hull[sz-1]-hull[sz-2])>=0){
hull.pop_back();
sz--;
}
hull.pb(p);
sz++;
}
sz--;
hull.pop_back();
reverse(a.begin(),a.end());
}
return hull;
}
vector<pt> Merge(vector<pt> a,vector<pt> b){
for(pt p:b)a.pb(p);
return ConvexHull(a);
}
vector<pt> Neg(vector<pt> a){
for(pt&p:a)p=-p;
return ConvexHull(a);
}
int get_minpt(vector<pt>&a){
int id=0;
for(int i=1;i<a.size();i++)
if(a[i]<a[id])id=i;
return id;
}
vector<pt> Minkowski(vector<pt>a,vector<pt>b){
if(a.size()>b.size())swap(a,b);
if(a.size()==1){
for(int i=0;i<b.size();i++)b[i]=b[i]+a[0];
return b;
}
int id=get_minpt(a);
rotate(a.begin(),a.begin()+id,a.end());
id=get_minpt(b);
rotate(b.begin(),b.begin()+id,b.end());
a.pb(a[0]);
a.pb(a[1]);
b.pb(b[0]);
b.pb(b[1]);
int pta=0;
int ptb=0;
vector<pt>ret;
while( !(pta==a.size()-2 && ptb==b.size()-2) ){
ret.pb(a[pta]+b[ptb]);
ll val=cross((a[pta+1]-a[pta]),(b[ptb+1]-b[ptb]));
if(val>=0)pta++;
if(val<=0)ptb++;
}
return ret;
}
/*
vector<pt> Minkowski(vector<pt> a,vector<pt> b){
if(a.empty())return b;
if(b.empty())return a;
if(a.size()==1||b.size()==1){
if(b.size()==1)swap(a,b);
for(pt&p:b)p=p+a[0];
return b;
}
vector<pt> ans;
ans.pb(a[0]+b[0]);
int i=0,j=0;
int n=a.size();
int m=b.size();
while(i<n||j<m){
if(j==m||(i<n && cross(a[(i+1)%n]-a[i],b[(j+1)%m]-b[j])>0)){
ans.pb(ans.back()+a[(i+1)%n]-a[i]);
i++;
}else{
ans.pb(ans.back()+b[(j+1)%m]-b[j]);
j++;
}
}
ans.pop_back();
return ConvexHull(ans);
*/
void Print(vector<pt> hull){
for(pt p:hull)printf("(%lld, %lld) ",p.x,p.y);
printf("\n");
}
const int N=10050;
vector<int> E[N];
vector<pt> hull[N];
void Solve(int u){
vector<pt> neg;
bool first=true;
for(int v:E[u]){
Solve(v);
//printf("Neg %i\n",v);
//Print(Neg(hull[v]));
if(!first){
hull[u]=Minkowski(hull[u],Neg(hull[v]));
}
//Print(hull[u]);
hull[u]=Merge(hull[u],Minkowski(neg,hull[v]));
neg=Minkowski(neg,Neg(hull[v]));
//Print(hull[u]);
first=false;
}
//printf("Final %i\n",u);
//Print(hull[u]);
}
int main(){
int n;
scanf("%i",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%i",&k);
if(k==0){
int x,y;
scanf("%i %i",&x,&y);
hull[i].pb(pt(x,y));
}else{
E[i].resize(k);
for(int&j:E[i])scanf("%i",&j);
}
}
Solve(1);
ll ans=0;
for(pt p:hull[1])ans=max(ans,sq(p));
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
5 4 2 3 4 5 0 2 -2 0 1 3 0 4 -6 0 -18 5