QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357535 | #5111. Take On Meme | TadijaSebez | WA | 1ms | 4588kb | C++14 | 2.6kb | 2024-03-18 22:59:45 | 2024-03-18 22:59:46 |
Judging History
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);
}
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: 100
Accepted
time: 1ms
memory: 4300kb
input:
5 4 2 3 4 5 0 2 -2 0 1 3 0 4 -6 0 -18 5
output:
725
result:
ok single line: '725'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
5 2 2 3 2 4 5 0 1 5 0 -4 -6 0 -1 7
output:
340
result:
ok single line: '340'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 4588kb
input:
18 3 4 3 2 2 5 6 3 7 9 8 3 10 11 12 0 4 -1 0 18 49 0 -2 10 2 13 14 0 -5 6 0 5 8 4 15 16 17 18 0 17 3 0 3 -9 0 -7 -1 0 14 -33 0 -23 11 0 11 14 0 2 19
output:
12325
result:
wrong answer 1st lines differ - expected: '26269', found: '12325'