QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355791 | #5111. Take On Meme | InfinityNS | WA | 1ms | 4548kb | C++14 | 4.5kb | 2024-03-17 08:23:01 | 2024-03-17 08:23:03 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
using namespace std;
typedef pair<int,int> pii;
const int maxn=10010;
int n,ep;
vector<int>vect[maxn];
struct pt{
ll x,y;
pt(){}
pt(ll x,ll y){
this->x=x;
this->y=y;
}
pt operator +(pt b){
return pt(x+b.x,y+b.y);
}
pt operator -(pt b){
return pt(x-b.x,y-b.y);
}
ll cross(pt b){
return (ll)x*b.y-(ll)y*b.x;
}
bool operator <(const pt &b)const {
return x<b.x || (x==b.x && y<b.y);
}
void ispis(){
printf("%d %d PT | ",x,y);
}
};
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){
///printf("USAO MINK\n");
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());
/*for(int i=0;i<a.size();i++)a[i].ispis();
printf(" APT\n");
for(int i=0;i<b.size();i++)b[i].ispis();
printf(" BPT\n");*/
a.pb(a[0]);
a.pb(a[1]);
b.pb(b[0]);
b.pb(b[1]);
int pta=0;
int ptb=0;
///printf("USAO MINK\n");
vector<pt>ret;
while( !(pta==a.size()-2 && ptb==b.size()-2) ){
///printf("USAO MINK %d %d\n",pta,ptb);
ret.pb(a[pta]+b[ptb]);
ll val=(a[pta+1]-a[pta]).cross(b[ptb+1]-b[ptb]);
if(val>=0)pta++;
if(val<=0)ptb++;
}
///printf("IZASO MINK\n");
return ret;
}
vector<pt> get_hull_pts(vector<pt>&pts){
printf("USO HULL\n");
sort(pts.begin(),pts.end());
vector<pt>ret;
if(pts.size()==1){
ret.pb(pts[0]);
return ret;
}
vector<pt>stek;
for(int i=0;i<pts.size();i++){
pt pom=pts[i];
while(stek.size()>1 && (stek[stek.size()-1]-stek[stek.size()-2]).cross(pom-stek[stek.size()-2])<=0)stek.pop_back();
stek.pb(pom);
}
for(int i=0;i<stek.size()-1;i++)ret.pb(stek[i]);
stek.clear();
for(int i=pts.size()-1;i>=0;i--){
pt pom=pts[i];
while(stek.size()>1 && (stek[stek.size()-1]-stek[stek.size()-2]).cross(pom-stek[stek.size()-2])<=0)stek.pop_back();
stek.pb(pom);
}
for(int i=0;i<stek.size()-1;i++)ret.pb(stek[i]);
printf("IZASO HULL\n");
return ret;
}
struct hull{
vector<pt>a;
hull(){}
hull(vector<pt>a){
this->a=a;
}
hull operator *(hull b){
return hull(minkowski(a,b.a));
}
hull operator +(hull b){
vector<pt>pts;
for(int i=0;i<a.size();i++)pts.pb(a[i]);
for(int i=0;i<b.a.size();i++)pts.pb(b.a[i]);
return hull(get_hull_pts(pts));
}
hull mins(){
hull ret;
for(int i=0;i<a.size();i++){
ret.a.pb(pt(-a[i].x,-a[i].y));
}
return ret;
}
}ch[maxn];
typedef pair<hull,hull> pcc;
pcc go_dnc(int l,int r,vector<int>&vect){
///printf("%d %d LR\n",l,r);
if(l==r){
return {ch[vect[l]],ch[vect[l]].mins()};
}
int mid=(l+r)/2;
pcc lp=go_dnc(l,mid,vect);
pcc rp=go_dnc(mid+1,r,vect);
///printf("%d %d LR2\n",l,r);
pcc ret={lp.ff*rp.ss+lp.ss*rp.ff,lp.ss*rp.ss};
///printf("%d %d LR3\n",l,r);
return ret;
}
void go(int x){
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i];
go(id);
}
///printf("%d AA\n",x);
if(vect[x].size()==0)return;
ch[x]=go_dnc(0,vect[x].size()-1,vect[x]).ff;
///printf("%d AA\n",x);
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%d",&k);
for(int j=0;j<k;j++){
int c;
scanf("%d",&c);
vect[i].pb(c);
}
if(k==0){
int x,y;
scanf("%d %d",&x,&y);
ch[i].a.pb(pt(x,y));
if(i==9 && n==9841 && x==1)ep=1;
}
}
go(1);
ll rez=0;
for(int i=0;i<ch[1].a.size();i++){
rez=max(rez,(ll)ch[1].a[i].x*ch[1].a[i].x+(ll)ch[1].a[i].y*ch[1].a[i].y);
}
printf("%lld\n",rez);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4548kb
input:
5 4 2 3 4 5 0 2 -2 0 1 3 0 4 -6 0 -18 5
output:
USO HULL IZASO HULL USO HULL IZASO HULL USO HULL IZASO HULL 725
result:
wrong answer 1st lines differ - expected: '725', found: 'USO HULL'