QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#735747 | #7906. Almost Convex | futarian | WA | 373ms | 4212kb | C++11 | 2.9kb | 2024-11-11 21:32:00 | 2024-11-11 21:32:00 |
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;
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);
}
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);
/*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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4092kb
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: 3964kb
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: 3948kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4212kb
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: 4032kb
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: 373ms
memory: 3976kb
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:
1670
result:
wrong answer 1st numbers differ - expected: '718', found: '1670'