QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#759660 | #7906. Almost Convex | futarian | WA | 1ms | 4532kb | C++11 | 3.2kb | 2024-11-18 11:00:56 | 2024-11-18 11:00:57 |
Judging History
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);
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];
}
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,)
}
sort(p + 1 , p + 1 + n , cmp);
/*if(i == 7)
{
printf("/AOI%lf %lf",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 == 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: 4500kb
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: 4496kb
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: 4332kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 4532kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
6
result:
wrong answer 1st numbers differ - expected: '7', found: '6'