QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759615#7906. Almost ConvexfutarianWA 568ms4200kbC++113.0kb2024-11-18 10:30:272024-11-18 10:30:28

Judging History

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

  • [2024-11-18 10:30:28]
  • 评测
  • 测评结果:WA
  • 用时:568ms
  • 内存:4200kb
  • [2024-11-18 10:30:27]
  • 提交

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;
	int id;
	V(){x = y = 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)
{
	db d = (x - P1) ^ (y - P1);
	if(abs(d) > eps) return d > 0;
	return len(x - P1) - len(y - P1) < eps;
}
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);
		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];
		}
		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;
	for(int i = 1 ; i <= n ; i ++) 
	{
		if(flg[i]) continue;
		for(int j = 1 ; j <= n ; j ++) p[j] = pp[j];
		P1 = p[i];
		stable_sort(p + 1 , p + 1 + n , cmp);
		stable_sort(p + 1 , p + 1 + n , cmp);
		stable_sort(p + 1 , p + 1 + n , cmp);
		/*if(i == 7)
		{
			for(int j = 1 ; j <= n ; j ++) printf("/ai%lf %lf\n",p[j].x,p[j].y);
		}*/
		for(int j = 1 ; j <= n ; 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]) == n - 2) 
			{
				/*if(i == 7)
				{
					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: 1ms
memory: 3936kb

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: 0ms
memory: 4016kb

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: 0ms
memory: 3944kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 0ms
memory: 4068kb

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: 568ms
memory: 4032kb

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:

1746

result:

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