QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792871#9520. Concave Hullliqingyang#WA 0ms3832kbC++172.2kb2024-11-29 14:49:002024-11-29 14:49:05

Judging History

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

  • [2024-11-29 14:49:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-11-29 14:49:00]
  • 提交

answer

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct point
{
	int x,y;
};
inline bool operator <(const point &a,const point &b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline point operator -(const point &a,const point &b)
{
	return {a.x-b.x,a.y-b.y};
}
inline long long operator *(const point &a,const point &b)
{
	return (long long)a.x*b.y-(long long)a.y*b.x;
}
int T,n,head,sta[100010];
point a[100010];
bool mark[100010];
inline long long calc(int x,int y,int z)
{
	return (a[y]-a[x])*(a[z]-a[x]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y;
			mark[i]=0;
		}
		sort(a+1,a+n+1);
		vector<int> v,V;
		sta[head=1]=1;
		for(int i=2;i<=n;i++)
		{
			while(head>1&&(a[sta[head]]-a[sta[head-1]])*
			(a[i]-a[sta[head-1]])>0)
			{
				head--;
			}
			sta[++head]=i;
		}
		for(int i=1;i<=head;i++)
		{
			v.emplace_back(sta[i]);
			mark[sta[i]]=1;
		}
		sta[head=1]=n;
		for(int i=n-1;i;i--)
		{
			while(head>1&&(a[sta[head]]-a[sta[head-1]])*
			(a[i]-a[sta[head-1]])>0)
			{
				head--;
			}
			sta[++head]=i;
		}
		for(int i=2;i<head;i++)
		{
			v.emplace_back(sta[i]);
			mark[sta[i]]=1;
		}
		if(v.size()==n)
		{
			cout<<-1<<endl;
			continue;
		}
		head=0;
		for(int i=1;i<=n;i++)
		{
			if(mark[i])
			{
				continue;
			}
			while(head>1&&(a[sta[head]]-a[sta[head-1]])*
			(a[i]-a[sta[head-1]])>0)
			{
				head--;
			}
			sta[++head]=i;
		}
		for(int i=1;i<=head;i++)
		{
			V.emplace_back(sta[i]);
		}
		head=0;
		for(int i=n;i;i--)
		{
			if(mark[i])
			{
				continue;
			}
			while(head>1&&(a[sta[head]]-a[sta[head-1]])*
			(a[i]-a[sta[head-1]])>0)
			{
				head--;
			}
			sta[++head]=i;
		}
		for(int i=2;i<head;i++)
		{
			V.emplace_back(sta[i]);
		}
		long long ans=9e18;
		for(int i=0,j=0;i<v.size();i++)
		{
			while(calc(v[i],v[(i+1)%v.size()],V[j])>
			calc(v[i],v[(i+1)%v.size()],V[(j+1)%V.size()]))
			{
				j=(j+1)%V.size();
			}
			ans=min(ans,-calc(v[i],v[(i+1)%v.size()],V[j]));
		}
		ans*=-1;
		for(int i=0;i<v.size();i++)
		{
			ans-=calc(0,v[i],
			v[(i+1)%v.size()]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3832kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

35
-1

result:

wrong answer 1st lines differ - expected: '40', found: '35'