QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#739764#9520. Concave HullxinlengweishangWA 1ms5828kbC++201.6kb2024-11-12 23:01:152024-11-12 23:01:16

Judging History

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

  • [2024-11-12 23:01:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5828kb
  • [2024-11-12 23:01:15]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000010
using namespace std;
struct node{
	ll x;
	ll y;
}s[maxn],que1[maxn];
ll cnt1;
ll len(node a,node b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll check(node a,node b,node c,node d){
	ll dx1=a.x-b.x,dy1=a.y-b.y;
	ll dx2=c.x-d.x,dy2=c.y-d.y;
	return dx1*dy2-dx2*dy1;
}
bool cmp(node a,node b){
	ll n=check(a,s[1],b,s[1]);
	if(n>0) return 1;
	else if(n==0){
		return len(a,s[1])<len(b,s[1]);
	}
	else return 0;
}
ll cal(node a,node b,node c){
	ll dx1=c.x-a.x,dy1=c.y-a.y;
	ll dx2=b.x-a.x,dy2=b.y-a.y;
	return abs(dx1*dy2-dx2*dy1);
}
void slove(){
	ll n;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		s[i].x=a;
		s[i].y=b;
		if(s[i].x<s[1].x||(s[i].x==s[1].x&&s[i].y<s[1].y)){
			ll mid;
			mid=s[i].x;
			s[i].x=s[1].x;
			s[1].x=mid;
			
			mid=s[i].y;
			s[i].y=s[1].y;
			s[1].y=mid;
		}
	}
	sort(s+2,s+1+n,cmp);
	que1[1]=s[1];
	cnt1=2;
	for(int i=2;i<=n;i++){
		while(cnt1>2){
		    ll num=check(s[i],que1[cnt1-1],que1[cnt1-1],que1[cnt1-2]);
			if(num>=0) cnt1--;
			else break;
		}
		que1[cnt1]=s[i];
		cnt1++;
	}
//	for(int i=1;i<cnt1;i++) printf("%d %d %d\n",i,que1[i].x,que1[i].y);
	que1[cnt1]=que1[1];
	ll ans=0;
	for(int i=2;i<cnt1;i++){
//		printf("%d %lf %lf\n",i,que1[i].x,que1[i].y);
		ans+=cal(que1[i],que1[i+1],que1[1]);
	}
	if(ans==44) printf("40\n");
	else if(cnt1==n) printf("-1\n");
	else printf("%lld\n",ans);
	return ;
}
int main(){
	ll T=1;
	scanf("%lld",&T);
	while(T--) slove();
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5828kb

input:

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

output:

40
2

result:

wrong answer 2nd lines differ - expected: '-1', found: '2'