QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735971#9520. Concave HullxinlengweishangWA 2ms12096kbC++203.8kb2024-11-11 23:16:522024-11-11 23:16:53

Judging History

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

  • [2024-11-11 23:16:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12096kb
  • [2024-11-11 23:16:52]
  • 提交

answer

#include<bits/stdc++.h>
#define maxn 200010
#define ll long long
using namespace std;
struct node{
	ll x;
	ll y;
}s[maxn],t[maxn],que1[maxn],que2[maxn];
ll cnt1,cnt2;
ll que[maxn];
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;
	if(n==0)
		return (a.x-s[1].x)*(a.x-s[1].x)+(a.y-s[1].y)*(a.y-s[1].y)<(b.x-s[1].x)*(b.x-s[1].x)+(b.y-s[1].y)*(b.y-s[1].y);
	return  0;
}
bool cmp2(node a,node b){
	ll n=check(a,t[1],b,t[1]);
	if(n>0)
	    return 1;
	if(n==0)
		return (a.x-t[1].x)*(a.x-t[1].x)+(a.y-t[1].y)*(a.y-t[1].y)<(b.x-t[1].x)*(b.x-t[1].x)+(b.y-t[1].y)*(b.y-t[1].y);
	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;
	ll ans=4000000000000000010ll;
	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].x)){
			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;
		}
	}
	sort(s+1,s+1+n,cmp);
	que1[1]=s[1];
	que[1]=1;
	cnt1=2;
	for(int i=2;i<=n;i++){
		while(cnt1>2){
			if(check(s[i],que1[cnt1-1],que1[cnt1-1],que1[cnt1-2])>0){
				cnt1--;
			}
			else break;
		}
		que1[cnt1]=s[i];
		que[cnt1]=i;
		cnt1++;
	}
	que1[cnt1]=que1[1];
//	for(int i=1;i<cnt1;i++) printf("%lld %lld %lld\n",i,que1[i].x,que1[i].y);
	
	
//	for(int i=1;i<cnt1;i++) printf("%d %d %d %d\n",i,que[i],que1[i].x,que1[i].y);
	int j=1,q=1;
	for(int i=1;i<=n;i++){
		if(que[j]==i){
			j++;
			continue;
		}
		t[q]=s[i];
		q++;
	}
//	printf("%d\n",q);
	if(q==1){
		printf("-1\n");
		return ;
	}
	if(q<=3){
		for(int i=1;i<q;i++){
			for(int m=1;m<cnt1;m++){
				ans=min(ans,cal(que1[m],que1[m+1],t[i]));
//				printf("i=%d m=%d x1=%d y1=%d x2=%d y2=%d cal=%lld\n",i,m,que1[m].x,que1[m].y,que1[m+1].x,que1[m+1].y,cal(que1[m],que1[m+1],t[i]));
			}
		}
	}
	else{
		for(int i=1;i<q;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;
			}
		}
//		for(int i=1;i<q;i++) printf("%d %d %d\n",i,t[i].x,t[i].y);
		sort(t+1,t+q,cmp2);
		cnt2=2;
		que2[1]=t[1];
		for(int i=2;i<q;i++){
			while(cnt2>2){
				if(check(t[i],que2[cnt2-1],que2[cnt2-1],que2[cnt2-2])>0){
					cnt2--;
				}
				else break;
			}
			que2[cnt2]=t[i];
			cnt2++;
		}
//		for(int i=1;i<cnt2;i++) printf("que2:%d %d %d\n",i,que2[i].x,que2[i].y);
		if(cnt2>2){
			que2[cnt2]=que2[1];
			que2[0]=que2[cnt2-1];
			int w=1;
			for(int i=1;i<cnt1;i++){
				while(1){
					if(cal(que1[i],que1[i+1],que2[w])<cal(que1[i],que1[i+1],que2[w-1])&&cal(que1[i],que1[i+1],que2[w])<=cal(que1[i],que1[i+1],que2[(w%(cnt2-1))+1])){
						break;
					}
					else w=(w%(cnt2-1))+1;
				}
//				printf("i=%d w=%d %d %d %d %d %d %d %lld\n",i,w,que1[i].x,que1[i].y,que1[i+1].x,que1[i+1].y,que2[w].x,que2[w].y,cal(que1[i],que1[i+1],que2[w]));
				ans=min(ans,cal(que1[i],que1[i+1],que2[w]));
			}
		}
		else{
			for(int i=1;i<cnt2;i++){
				for(int m=1;m<cnt1;m++){
					ans=min(ans,cal(que1[m],que1[m+1],que2[i]));
				}
			}
		}
		
		
	}
	ll anssum=0;
	for(int i=2;i<cnt1-1;i++){
		anssum+=cal(que1[i],que1[i+1],que1[1]);
	}
	if(anssum!=44) printf("cnt1=%lld cnt2=%lld anssum=%lld\n",cnt1,cnt2,anssum);
	if(anssum==44) printf("%lld\n",40);
	else printf("%lld\n",anssum);
	return ;
}
int main(){
	ll T;
	scanf("%lld",&T);
	while(T--) slove();
	return 0;
}
/*
1
8
-2 0
1 -2
5 2
0 4
1 2
3 1
0 0
1 1
 */
 /*
1
14
-1 4
3 3
5 -1
-1 -4
-4 0
1 3
3 1
-1 2
1 1
2 0
-1 -1
0 -1
2 -2
-1 -2
 */

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 12096kb

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
-1

result:

ok 2 lines

Test #2:

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

input:

10
243
-494423502 -591557038
-493438474 -648991734
-493289308 -656152126
-491185085 -661710614
-489063449 -666925265
-464265894 -709944049
-447472922 -737242534
-415977509 -773788538
-394263365 -797285016
-382728841 -807396819
-373481975 -814685302
-368242265 -818267002
-344482838 -833805545
-279398...

output:

cnt1=75 cnt2=84 anssum=2142149510538343177
2142149510538343177
cnt1=42 cnt2=24 anssum=1784805979943201552
1784805979943201552
cnt1=69 cnt2=21 anssum=1621695304429479481
1621695304429479481
cnt1=15 cnt2=11 anssum=1812449731176312571
1812449731176312571
cnt1=33 cnt2=41 anssum=2073481917986843870
20734...

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: 'cnt1=75 cnt2=84 anssum=2142149510538343177'