QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734490#7906. Almost ConvexxinlengweishangWA 496ms8208kbC++202.9kb2024-11-11 11:27:142024-11-11 11:27:14

Judging History

This is the latest submission verdict.

  • [2024-11-11 11:27:14]
  • Judged
  • Verdict: WA
  • Time: 496ms
  • Memory: 8208kb
  • [2024-11-11 11:27:14]
  • Submitted

answer

#include<bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;
struct node{
	ll x;
	ll y;
}t[maxn],s[maxn],sup[maxn],sdown[maxn];
ll x;
	ll n;
ll check(node a,node b,node c,node d){
	return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x);
}//叉积 如果大于0表示偏左 小于0偏右 
ll len(node a,node b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}//计算两点距离 保证无共线的话可以不写 
ll cmp(node a,node b){
	ll n=check(t[1],a,t[1],b);
	if(n==0)
		return len(t[1],a)>len(t[1],b);
	if(n>0) return 1;
	else return 0;
	 
}//仅用于凸包的极角排序 写死了第一个点作为基准点 


ll cmpup(node a,node b){
	ll n=check(t[x],a,t[x],b);
	if(n==0)
		return len(t[x],a)>len(t[x],b);
	if(n>0) return 1;
	else return 0;
}
ll cmpdown(node a,node b){
	ll n=check(t[x],a,t[x],b);
	if(n==0)
		return len(t[x],a)>len(t[x],b);
	if(n>0) return 1;
	else return 0;
}


map<ll,map<ll,ll> > mp;
ll sslove(){
	ll j=0,q=0;
	for(int i=1;i<=n;i++){
		if(t[i].y>t[x].y){
			sup[j]=t[i];
			j++;
		}
		else if(t[i].y==t[x].y){
			if(t[i].x>t[x].x){
			    sup[j]=t[i];
			    j++;
			}
			else if(t[i].x==t[x].x){
				continue;
			}
			else{
			    sdown[q]=t[i];
			    q++;
			}
		}
		else{
		    sdown[q]=t[i];
		    q++;
		}
	}//分组,y更大或者x大的在一侧 
	sort(sup,sup+j,cmpup);
	sort(sdown,sdown+q,cmpdown);
	ll ans=0;
	
	for(ll i=0;i<j-1;i++){
//		printf(" %lld %lld %lld\n",i,sup[i].x,sup[i].y);
		if(mp[sup[i].x][sup[i].y]&&mp[sup[i+1].x][sup[i+1].y]) ans++;
	}
//		printf(" %lld %lld %lld\n",j-1,sup[j-1].x,sup[j-1].y);
	for(ll i=0;i<q-1;i++){
//		printf(" %lld %lld %lld\n",i,sdown[i].x,sdown[i].y);
		if(mp[sdown[i].x][sdown[i].y]&&mp[sdown[i+1].x][sdown[i+1].y]) ans++;
	}
//		printf(" %lld %lld %lld\n",q-1,sdown[q-1].x,sdown[q-1].y);
		if(mp[sup[j-1].x][sup[j-1].y]==1&&mp[sdown[0].x][sdown[0].y]==1) ans++;
		if(mp[sup[0].x][sup[0].y]==1&&mp[sdown[q-1].x][sdown[q-1].y]==1) ans++;
//		printf("ans=%lld\n\n",ans);
	return ans; 
}


void slove(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		scanf("%lld%lld",&t[i].x,&t[i].y);
	}//读取每个点的x,y 
	for(ll i=2;i<=n;i++){
		if((t[i].y<t[1].y)||(t[i].y==t[1].y&&t[i].x<t[1].x)){
	        ll mid;
			mid=t[i].y;
			t[i].y=t[1].y;
			t[1].y=mid;
			mid=t[i].x;
			t[i].x=t[1].x;
			t[1].x=mid;
		}
	}//保证第一个点处于左下角,即一定在凸包上
	sort(t+2,t+1+n,cmp);
	s[1]=t[1];
	ll cnt=2;
	for(ll i=2;i<=n;i++){
		while(cnt>2){
			int n=check(s[cnt-2],s[cnt-1],s[cnt-1],t[i]);
			if(n<0){
				cnt--;
			}
			else {
				break;
			}
		}
		s[cnt]=t[i];
		cnt++;
	}
	for(int i=1;i<cnt;i++){
		mp[s[i].x][s[i].y]=1;
	}
	ll ans=0;
	for(int w=1;w<=n;w++){
		x=w;
		if(mp[t[w].x][t[w].y]) continue;
		ans+=sslove();
	}
	printf("%lld\n",ans+1);
	return ;
}
int main(){
	int T=1;
//  scanf("%d",&d);
	while(T--) slove();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 7924kb

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: 1ms
memory: 7868kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7868kb

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: 1ms
memory: 7988kb

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: 496ms
memory: 8208kb

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:

30462

result:

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