QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734565#7906. Almost ConvexxinlengweishangWA 0ms3920kbC++202.4kb2024-11-11 12:42:392024-11-11 12:42:40

Judging History

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

  • [2024-11-11 12:42:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3920kb
  • [2024-11-11 12:42:39]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define maxn 10010
using namespace std;
	ll n;
struct node{
	ll x;
	ll y;
}s[maxn],que[maxn],up[maxn],down[maxn];
ll check(node a,node b,node c){
	ll dx1=a.x-c.x,dy1=a.y-c.y;
	ll dx2=b.x-c.x,dy2=c.y-c.y;
	return dx1*dy2-dx2*dy1;
}
bool cmp(node a,node b){
	ll n=check(a,b,s[1]);
	if(n>0) return 1;
	else if(n==0)
		return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x);
	return 0;
}
//bool cmpup(node a,node b){
//	ll n=check(a,b,s[1]);
//	if(n>0) return 1;
//	else if(n==0)
//		return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x)
//	else return 0;
//}
//bool cmpdown(node a,node b){
//	ll n=check(a,b,s[1]);
//	if(n>0) return 1;
//	else if(n==0)
//		return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x)
//	else return 0;
//}
map<ll,map<ll,ll> > mp;
int check2(node a,node b){
	if(mp[a.x][a.y]==1&&mp[b.x][b.y]==1) return 1;
	return 0;
}
ll sslove(int x){
	ll ans=0;
	ll mid;
	mid=s[x].x;
	s[x].x=s[1].x;
	s[1].x=mid;
	mid=s[x].y;
	s[x].y=s[1].y;
	s[1].y=mid;
	ll j=1,q=1;
	for(int i=2;i<=n;i++){
		if(s[i].y>s[1].y){
			up[j]=s[i];
			j++;
		}
		else if(s[i].y==s[1].y){
			if(s[i].x>s[1].x){
				up[j]=s[i];
				j++;
			}
			else {
				down[q]=s[i];
				q++;
			}
		}
		else {
			down[q]=s[i];
			q++;
		}
	}
	sort(up+1,up+j,cmp);
	sort(down+1,down+q,cmp);
	for(int i=1;i<j-1;i++){
		if(check2(up[i],up[i+1])) ans++;
	}
	for(int i=1;i<q-1;i++){
		if(check2(down[i],down[i+1])) ans++;
	}
	if(check2(up[j-1],down[0])) ans++;
	if(check2(up[0],down[q-1])) ans++;
	return ans;
}
void slove(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&s[i].x,&s[i].y);
		if(s[i].y<s[1].y||((s[i].y==s[1].y)&&(s[i].x<s[1].y))){
			ll mid;
			
			mid=s[i].y;
			s[i].y=s[1].y;
			s[1].y=mid;
			
			mid=s[i].x;
			s[i].x=s[1].x;
			s[1].x=mid;
		}//保证左下角的点位于s[1] 
	}
	sort(s+2,s+n+1,cmp);
	ll cnt=2;
	que[1]=s[1];
	for(int i=2;i<=n;i++){
		while(cnt>2){
			if(check(s[i],que[cnt-1],que[cnt-2])){
				cnt--;
			}
			else break;
		}
		que[cnt]=s[i];
		cnt++;
	}
	for(int i=1;i<cnt;i++){
		mp[que[i].x][que[i].y]=1;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(mp[s[i].x][s[i].y]) continue;
		ans+=sslove(i);
	}
	printf("%lld",ans);
	return ;
}
int main(){
	int T=1;
	while(T--) slove();
	return 0;
}
/*
7
1 4
4 0
2 3
3 1
3 5
0 0
2 4
*/

详细

Test #1:

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

input:

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

output:

11

result:

wrong answer 1st numbers differ - expected: '9', found: '11'