QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426553#7906. Almost Convexyuanyq5523WA 1ms3988kbC++171.7kb2024-05-31 15:08:502024-05-31 15:08:51

Judging History

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

  • [2024-05-31 15:08:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3988kb
  • [2024-05-31 15:08:50]
  • 提交

answer

#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e3+3;
const double eps=1e-12;
int n,top,ans,rk[N];
bool flag[N];
struct point{double x,y; int idx;}p[N],s[N],Pole;
vector<point>tubao;
point operator+(point& a,point& b){return point({a.x+b.x,a.y+b.y,0});}
point operator-(point& a,point& b){return point({a.x-b.x,a.y-b.y,0});}
double cross(point a,point b,point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double cross(point a,point b){return a.x*b.y-b.x*a.y;}
bool cmp1(point a,point b){
    return cross(a-Pole,b-Pole)>0;
}
bool cmp2(point a,point b){
	if (a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}
void Andrew(){
	sort(p+1,p+n+1,cmp2);
	for (int i=1;i<=n;i++){
		while (top>1 && cross(s[top-1],s[top],p[i])<=0) top--;
		s[++top]=p[i];
	}
	int t=top;
	for (int i=n-1;i>=1;i--){
		while (top>t && cross(s[top-1],s[top],p[i])<=0) top--;
		s[++top]=p[i];
	}
	for (int i=1;i<=top;i++){
		tubao.push_back(s[i]);
		flag[s[i].idx]=true;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
		p[i].idx=i;
	}
	Andrew();
	for (int i=1;i<=n;i++){
		if (flag[p[i].idx]) continue;
		Pole=p[i]; vector<point>tmp;
		for (int j=1;j<=n;j++){
			if (p[j].idx==Pole.idx) continue;
			tmp.push_back(p[j]);
		}
		sort(tmp.begin(),tmp.end(),cmp1);
		for (int j=0;j<n-1;j++){
			rk[tmp[j].idx]=j;
		}
		for (int j=0;j<top-1;j++){
			int idx1=tubao[j].idx;
			int idx2=tubao[j+1].idx;
			if ((rk[idx1]+1)%(n-1)==rk[idx2] || (rk[idx2]+1)%(n-1)==rk[idx1]) ans++;
		}
		//cout<<p[i].idx<<" "<<ans<<endl;
	}
	cout<<ans+1<<endl;
	return 0;
}

详细

Test #1:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3700kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

6

result:

wrong answer 1st numbers differ - expected: '7', found: '6'