QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759704#7906. Almost ConvexfutarianWA 416ms4704kbC++113.4kb2024-11-18 11:22:152024-11-18 11:22:16

Judging History

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

  • [2024-11-18 11:22:16]
  • 评测
  • 测评结果:WA
  • 用时:416ms
  • 内存:4704kb
  • [2024-11-18 11:22:15]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define il inline
#define db double
const int Len = 2e3 + 5;
const db eps = 1e-10;
int n,m,flg[Len];
struct V
{
	double x,y,ang;
	int id;
	V(){x = y = ang = 0.0 , id = 0;}
	V(db X,db Y){x = X , y = Y;}
}p[Len],pp[Len];
il V operator + (V x,V y){return V(x.x + y.x , x.y + y.y);}
il V operator - (V x,V y){return V(x.x - y.x , x.y - y.y);}
il V operator * (V x,db a){return V(x.x * a , x.y * a);}
il V operator / (V x,db a){return V(x.x / a , x.y / a);} 
il bool eq(db x,db y){return abs(x - y) < eps;}
il bool operator == (V x,V y){return eq(x.x , y.x) && eq(x.y , y.y);}
il bool operator != (V x,V y){return !eq(x.x , y.x) && !eq(x.y , y.y);}
il db operator * (V x,V y){return x.x * y.x + x.y * y.y;}
il db operator ^ (V x,V y){return x.x * y.y - x.y * y.x;}
il bool operator < (V x,V y){return x.x < y.x - eps && x.y < y.y - eps;}
il db len(V x){return sqrt(x.x * x.x + x.y * x.y);}
il V mid(V x,V y){return V((x.x + y.x) / 2.0 , (x.y + y.y) / 2.0);}
il V vc(V x){return V(-x.y , x.x);}
il V dw(V x){return V(x.x / len(x) , x.y / len(x));}
il db S(V x,V y,V z){return abs((y - x) ^ (z - x)) / 2.0;}
V stk[Len];int top = 0;
V P1;
il bool cmp(V x,V y)
{
	if(abs(x.ang - y.ang) > eps) return x.ang < y.ang;
	return len(x - P1) - len(y - P1) < 0;
}
struct CONVEXHULL
{
	V P[Len];int N;
	inline void init(V *p,int n)
	{
		N = n;
		for(int i = 1 ; i <= N ; i ++) P[i] = p[i];
	}
	inline void Init()
	{
		top = 0;P1 = V(0 , 0);for(int i = 1 ; i <= N ; i ++) P[i].ang = atan2((P[i] - P1).y , (P[i] - P1).x);
		stable_sort(P + 1 , P + 1 + N , cmp);
		for(int i = 1 ; i <= N ; i ++) 
		{
			while(top > 1 && ((stk[top] - stk[top - 1]) ^ (P[i] - stk[top - 1])) < eps) top --;
			stk[++ top] = P[i];
		} 
		N = top;for(int i = 1 ; i <= N ; i ++) 
		{
			flg[stk[i].id] = 1;
			P[i] = stk[i];
			//printf("!%lf %lf\n",P[i].x,P[i].y);
		}
		P[N + 1] = P[1];
	}
	inline double LEN(){double ds = 0;for(int i = 1 ; i <= N ; i ++) ds += len(P[i] - P[i - 1]);return ds;}
}CV;
int pos[Len];
inline int Iabs(int x){if(x < 0) x = -x;return x;}
signed main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; i ++) 
	{
		scanf("%lf %lf",&p[i].x,&p[i].y);
		p[i].id = i;
		pp[i] = p[i];
	}
	CV.init(p , n);
	CV.Init();
	//for(int i = 1 ; i <= CV.N ; i ++) printf("??%lf %lf\n",CV.P[i].x,CV.P[i].y);
	int as = 0 , ct = 0;
	for(int i = 1 ; i <= n ; i ++) 
	{
		if(flg[i]) continue;
		ct = 0;
		for(int j = 1 ; j <= n ; j ++) 
		{
			if(j == i) continue;
			p[++ ct] = pp[j];
		}
		/*if(i == 5)
		{
			for(int j = 1 ; j <= ct ; j ++) printf("/aoi%lf %lf %lf\n",p[j].x,p[j].y,p[j].ang);
		}*/
		P1 = pp[i];
		for(int j = 1 ; j <= ct ; j ++) 
		{
			p[j].ang = atan2((p[j] - P1).y , (p[j] - P1).x);
			//printf("woee%lf %lf %lf\n",p[j].ang,)
		}
		stable_sort(p + 1 , p + 1 + ct , cmp);
		/*if(i == 5)
		{
			printf("/AOI%lf %lf\n",P1.x,P1.y);
			for(int j = 1 ; j <= ct ; j ++) printf("/aoi%lf %lf %lf\n",p[j].x,p[j].y,p[j].ang);
		}*/
		for(int j = 1 ; j <= ct ; j ++) pos[p[j].id] = j;
		for(int j = 1 ; j <= CV.N ; j ++) 
		{
			if(Iabs(pos[CV.P[j].id] - pos[CV.P[j + 1].id]) == 1 || Iabs(pos[CV.P[j].id] - pos[CV.P[j + 1].id]) == ct - 1) 
			{
				/*if(i == 5)
				{
					printf("%lf %lf %lf %lf\n",CV.P[j].x,CV.P[j].y,CV.P[j + 1].x,CV.P[j + 1].y);
				}*/
				as ++;
			}
		}
	}
	printf("%d\n",as + 1);
	return 0;
}

详细

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

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: 416ms
memory: 4672kb

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:

947

result:

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