QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426610#7906. Almost Convexyuanyq5523WA 377ms3788kbC++171.6kb2024-05-31 16:15:472024-05-31 16:15:47

Judging History

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

  • [2024-05-31 16:15:47]
  • 评测
  • 测评结果:WA
  • 用时:377ms
  • 内存:3788kb
  • [2024-05-31 16:15:47]
  • 提交

answer

#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e3+3;
int n,top,ans,rk[N],cur;
bool flag[N];
struct point{LL x,y; int idx;}p[N],s[N],tmp[N],P,O;
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});}
LL cross(point a,point b,point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
LL cross(point a,point b){return a.x*b.y-b.x*a.y;}
bool cmp1(point A,point B){
	LL tmp1=cross(P-O,A-O),tmp2=cross(P-O,B-O);
    if ((tmp1>0)!=(tmp2>0)) return tmp1>tmp2;
    return cross(A-O,B-O)>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++){
		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;
		cur=0;
		O=p[i]; P={p[i].x-1,p[i].y,p[i].idx}; 
		for (int j=1;j<=n;j++){
			if (p[j].idx==O.idx) continue;
			tmp[++cur]=p[j];
		}
		sort(tmp+1,tmp+cur+1,cmp1);
		for (int j=0;j<n-1;j++) rk[tmp[j].idx]=j; 
		for (int j=1;j<top;j++){
			int idx1=s[j].idx;
			int idx2=s[j+1].idx;
			if ((rk[idx1]+1)%(n-1)==rk[idx2] || (rk[idx2]+1)%(n-1)==rk[idx1]) ans++;
		}
	}
	cout<<ans+1<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3680kb

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: 3692kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #5:

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 377ms
memory: 3788kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

654

result:

wrong answer 1st numbers differ - expected: '718', found: '654'