QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#539#332904#7906. Almost ConvexwYYSZLwYYSZLFailed.2024-02-19 18:22:502024-02-19 18:22:50

Details

Extra Test:

Accepted
time: 0ms
memory: 3900kb

input:

3
1 1
2 2
0 3

output:

1

result:

ok 1 number(s): "1"

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332904#7906. Almost ConvexwYYSZLAC ✓153ms4392kbC++142.6kb2024-02-19 16:25:012024-02-19 16:25:02

answer

#include<bits/stdc++.h>
#define int long long 
#define pi (3.1415926)
using namespace std;
int n;
int ans=1;
int x[2005],y[2005];
vector<int>xl;
int maxx=-1e7,maxi;
bool b[2005];
double deg(int a,int b){
	auto d=atan2(y[a]-y[b],x[a]-x[b]);
	if(d<0)d+=pi;
	return d;
}
double todeg(int a,int b,int c){
	// cout<<a<<' '<<b<<' '<<c<<'\n';
	double A=sqrtl((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])),
		B=sqrtl((x[a]-x[c])*(x[a]-x[c])+(y[a]-y[c])*(y[a]-y[c])),
		C=sqrtl((x[b]-x[c])*(x[b]-x[c])+(y[b]-y[c])*(y[b]-y[c]));
		// cerr<<x[a]-x[b]<<' '<<y[a]-y[b]<<'\n';
		// cerr<<A*A<<' '<<B*B<<' '<<C*C<<' '<<(A*A+B*B-C*C)/2/A/B<<'\n';
	double ans=acos((A*A+B*B-C*C)/2/A/B);
	while(ans<0)ans+=pi;
	while(ans>pi)ans-=pi;
	// cout<<a<<' '<<b<<' '<<c<<' '<<ans<<'\n';
	// cout<<ans<<'\n';
	return ans;
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	//freopen("1.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x[i]>>y[i];
		if(y[i]>maxx)
			maxx=y[i],maxi=i;
	}
	double mx=-1e7;int mi=0;
	for(int i=1;i<=n;++i){
		if(i==maxi)continue;
		if(x[i]==x[maxi])continue;
		double k=(y[i]-maxx)*1.0/(x[i]-x[maxi]);
		double b=y[i]-k*x[i];
		// cerr<<k<<' '<<b<<'\n';	
		int op=0;
		int bl=1;
		for(int j=1;j<=n;++j){
			if(j==i or j==maxi)continue;
			if(!op)op=(x[j]*k+b>y[j]?-1:1);
			else if(op!=(x[j]*k+b>y[j]?-1:1)){bl=0;break;}
		}
		if(bl){mi=i;break;}
	}
	int tp=mi,last=maxi;
	int st=maxi;
	xl.push_back(maxi);
	xl.push_back(mi);
	b[tp]=b[maxi]=1;
	while(1){
		double maxx=-114;
		int maxi=0;
		for(int i=1;i<=n;++i){
			if(b[i])continue;
			if(todeg(tp,last,i)>maxx)
				maxx=todeg(tp,last,i),maxi=i;
		}
		if(todeg(tp,last,st)>maxx)break;
		last=tp;
		tp=maxi;
		xl.push_back(tp);
		b[tp]=1;
	}
	// for(auto z:xl)cout<<x[z]<<' '<<y[z]<<'\n';
	int sz=xl.size()-1;
	for(int i=0;i<=sz;++i)xl.push_back(xl[i]);
		// cerr<<"\n-------------------------\n";
	for(int i=0;i<=sz;++i){
		vector<pair<double,double> >lx={};
			// cout<<xl[i]<<' '<<xl[i+1]<<'\n';
		for(int j=1;j<=n;++j){
			if(b[j])continue;
			// cout<<xl[i]<<' '<<xl[i+1]<<'\n';
			lx.push_back({todeg(xl[i],xl[i+1],j),\
				todeg(xl[i+1],xl[i],j)});
			// cout<<todeg(xl[i],xl[i+1],j)<<' '<<todeg(xl[i+1],xl[i],j)<<'\n';
		}
		sort(lx.begin(),lx.end());
		double miny=lx[0].second;
		for(int i=0;i<lx.size();++i){
			++ans;
			if(!i)continue;
			// if(lx[i].first>lx[i-1].first and lx[i].second>lx[i-1].second)
			// 	--ans;
			if(lx[i].second>miny)--ans;
			else miny=min(miny,lx[i].second);
		}
		// cout<<ans<<' ';
	}
	cout<<ans<<'\n';
	return 0;
}