QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357570#5111. Take On MemeInfinityNSRE 0ms0kbC++143.4kb2024-03-19 00:01:392024-03-19 00:01:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 00:01:41]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-03-19 00:01:39]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: