QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736449#9520. Concave HullxsdgpWA 1ms3908kbC++202.5kb2024-11-12 11:09:482024-11-12 11:09:57

Judging History

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

  • [2024-11-12 11:09:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3908kb
  • [2024-11-12 11:09:48]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m;
struct VECTOR
{
	double x,y;
	double operator^(const VECTOR &v)const
	{
		return x*v.y-y*v.x;
	}
};
struct POINT
{
	double x,y;
	bool operator<(const POINT &p)const
	{
		if(x==p.x)return y<p.y;
		else return x<p.x;
	}
	bool operator==(const POINT &p)const
	{
		return x==p.x&&y==p.y;
	}
	VECTOR operator-(const POINT &p)const
	{
		return {x-p.x,y-p.y};
	}
}p[100005],p1[100005];
int cross(VECTOR v1,VECTOR v2)
{
	return v1^v2;
}
vector<POINT> st,st1;
map<POINT,bool> mp;
bool check(POINT p)
{
	POINT back1=st.back(),back2=*(st.rbegin()+1);
	return cross(back1-back2,p-back1)<=0;
}
void andrew()
{
	st.clear();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)
	{
		while(st.size()>1&&check(p[i]))st.pop_back();
		st.push_back(p[i]);
	}
	int k=st.size();
	for(int i=n-1;i>=1;i--)
	{
		while(st.size()>k&&check(p[i]))st.pop_back();
		st.push_back(p[i]);
	}
	st.pop_back();
}
bool check1(POINT p)
{
	POINT back1=st1.back(),back2=*(st1.rbegin()+1);
	return cross(back1-back2,p-back1)<=0;
}
void andrew1()
{
	st1.clear();
	sort(p1+1,p1+m+1);
	for(int i=1;i<=m;i++)
	{
		while(st1.size()>1&&check1(p1[i]))st1.pop_back();
		st1.push_back(p1[i]);
	}
	int k=st1.size();
	for(int i=m-1;i>=1;i--)
	{
		while(st1.size()>k&&check1(p1[i]))st1.pop_back();
		st1.push_back(p1[i]);
	}
	st1.pop_back();
}
int rotcaliper()
{
	int j=0,sub=1e18;
	VECTOR v=st[1]-st[0];
	while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j+1)%st1.size();
	while(m!=1&&cross(v,st1[(j-1+st1.size())%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j-1+st1.size())%st1.size();
	for(int i=0;i<st.size();i++)
	{
		int i1=(i+1)%st.size();
		VECTOR v=st[i1]-st[i];
		while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[i])<=cross(v,st1[j]-st[i]))j=(j+1)%st1.size();
		sub=min(sub,cross(v,st1[j]-st[i]));
	}
	return sub;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].x>>p[i].y;
	andrew();
	int sum=0;
	for(int i=0;i<st.size();i++)
	{
		mp[st[i]]=1;
		POINT o={0,0};
		sum+=cross(st[i]-o,st[(i+1)%st.size()]-o);
	}
	m=0;
	for(int i=1;i<=n;i++)
		if(mp.find(p[i])==mp.end())p1[++m]=p[i];
	andrew1();
	
	if(m==0)cout<<-1<<endl;
	else cout<<sum-rotcaliper()<<endl;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)solve();
	return 0;
}
/*
3
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
5
-2 0
1 -2
5 2
0 4
3 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

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: -100
Wrong Answer
time: 1ms
memory: 3908kb

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:

2178418010787347730
1826413114144932218
1651687576234220015
1883871859778998916
2119126281997959816
894016174881844663
2271191316922159135
1998643358049669502
1740474221286618592
1168195646932543204

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178418010787347730'