QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333241#7906. Almost ConvexJohnAlfnovWA 0ms3992kbC++141.4kb2024-02-19 19:05:452024-02-19 19:05:45

Judging History

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

  • [2024-02-19 19:05:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3992kb
  • [2024-02-19 19:05:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int x[2005],y[2005];
long long cha(int a,int b,int c){
	return 1ll*(x[b]-x[a])*(y[c]-y[b])-1ll*(y[b]-y[a])*(x[c]-x[b]);
}
long long dian(int a,int b,int c){
	return 1ll*(x[b]-x[a])*(x[c]-x[a])+1ll*(y[b]-y[a])*(y[c]-y[a]);
}
int p[2005];
int st[2005];
int vist[2005];
struct apple{
	double a1,a2;
	bool operator<(const apple &other)const{
		if(a1==other.a1)return a2<other.a2;
		return a1<other.a1;
	}
}e[2005];
double dis(int a,int b){
	return sqrt(1.0*(x[a]-x[b])*(x[a]-x[b])+1.0*(y[a]-y[b])*(y[a]-y[b]));
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]),p[i]=i;
	sort(p+1,p+n+1,[&](int a,int b){
		if(x[a]==x[b])return y[a]<y[b];
		return x[a]<x[b];
	});
	int tt=0;
	st[++tt]=p[1];
	for(int i=2;i<=n;++i){
		while(tt>1&&cha(st[tt-1],st[tt],p[i])<=0)--tt;
		st[++tt]=p[i];
	}
	int t2=tt;
	for(int i=n-1;i>=1;--i){
		while(tt>t2&&cha(st[tt-1],st[tt],p[i])<=0)--tt;
		st[++tt]=p[i];
	}
	for(int i=1;i<tt;++i)vist[st[i]]=1;
	int ans=1;
	for(int i=1;i<tt;++i){
		int s=0;
		for(int j=1;j<=n;++j)if(!vist[j]){
			++s;
			e[s].a1=dian(st[i],st[i+1],j)/dis(st[i],j);
			e[s].a2=dian(st[i+1],st[i],j)/dis(st[i+1],j);
			if(i==1&&(j==3||j==4))cout<<e[s].a1<<" "<<e[s].a2<<endl;
		}
		sort(e+1,e+s+1);
		double mx=-1e18;
		for(int i=s;i>=1;--i){
			if(e[i].a2>=mx)++ans;
			mx=max(mx,e[i].a2);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

2.2188 2.2188
3.79473 2.82843
9

result:

wrong output format Expected integer, but "2.2188" found