QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357535#5111. Take On MemeTadijaSebezWA 1ms4588kbC++142.6kb2024-03-18 22:59:452024-03-18 22:59:46

Judging History

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

  • [2024-03-18 22:59:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4588kb
  • [2024-03-18 22:59:45]
  • 提交

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'