QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792837#9520. Concave Hullliqingyang#WA 22ms3660kbC++172.2kb2024-11-29 14:37:112024-11-29 14:37:11

Judging History

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

  • [2024-11-29 14:37:11]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3660kb
  • [2024-11-29 14:37:11]
  • 提交

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 abs((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=1e18;
		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: 100
Accepted
time: 0ms
memory: 3660kb

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:

40
-1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

2178418010787347715
1826413114144932145
1651687576234220014
1883871859778998985
2119126281997959892
894016174881844630
2271191316922158910
1998643358049669416
1740474221286618711
1168195646932543192

result:

ok 10 lines

Test #3:

score: -100
Wrong Answer
time: 22ms
memory: 3640kb

input:

1000
125
64661186 -13143076
302828013 -185438065
-418713797 -191594241
430218126 -397441626
354327250 -836704374
149668812 -598584998
311305970 66790541
199720625 -592356787
468137 -584752683
258775829 96211747
-358669612 -134890109
-129221188 -998432368
-277309896 -140056561
356901185 420557649
-51...

output:

1986320445246155278
1900093336073022078
1612088392301142476
2012259136539173407
1819942017252118749
1772230185841892196
1164835027347150174
1527446155241140517
1807368432185303666
1236918659444944569
1306839249967484778
1984123720246784099
1868728080720036006
667458140583450322
2127932992585026491
4...

result:

wrong answer 7th lines differ - expected: '1164835025329039520', found: '1164835027347150174'