QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584270 | #7906. Almost Convex | ggggggg | TL | 1ms | 6480kb | C++14 | 2.5kb | 2024-09-23 11:05:14 | 2024-09-23 11:05:14 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define sz(x) ((int)x.size())
const double eps=1e-8;
const double PI=acos(-1);
using namespace std;
int sgn(double x){
if(fabs(x)<eps) return 0;
if(x<0) return -1;
return 1;
}
struct Point{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
Point operator+(const Point &b)const{
return Point(x+b.x,y+b.y);
}
Point operator-(const Point&b)const{
return Point(x-b.x,y-b.y);
}
double operator*(const Point &b)const{
return x*b.x+y*b.y;
}
double operator^(const Point &b)const{
return x*b.y-y*b.x;
}//cross product
bool operator<(const Point &b)const{
return x<b.x||(x==b.x&&y<b.y);
}
bool operator==(const Point &b)const{
return sgn(x-b.x)==0&&sgn(y-b.y)==0;
}
Point rotate(Point b,double ang){//Rotate counterclockwise about point b by angle ang
Point tmp;
tmp.x=(x-b.x)*cos(ang)-(y-b.y)*sin(ang)+b.x;
tmp.y=(x-b.x)*sin(ang)+(y-b.y)*cos(ang)+b.y;
return tmp;
}
};
vector<Point> ConvexHull(vector<Point> P){
if(P.size()<3) return P;
int l=P.size(),tp=-1;
vector<Point> st;
st.resize(2*l);
sort(P.begin(),P.end());
st[++tp]=P[0],st[++tp]=P[1];
for(int i=2;i<l;i++){
while(tp>=1&&sgn((st[tp]-st[tp-1])^(P[i]-st[tp]))<=0) tp--;
st[++tp]=P[i];
}
st[++tp]=P[l-2];
int cur=tp;
for(int i=l-3;i>=0;i--){
while(tp>=cur&&sgn((st[tp]-st[tp-1])^(P[i]-st[tp]))<=0) tp--;
st[++tp]=P[i];
}
st.resize(tp);
return st;
}
const int N=2005;
int n,a[N][N],b[N][N],id[N],vs[N];
int main(){
scanf("%d",&n);
vector<Point> p;
p.resize(n);
rep(i,0,n-1) scanf("%lf%lf",&p[i].x,&p[i].y);
vector<Point> p1=ConvexHull(p);
rep(i,0,n-1){
int l=0;
rep(j,0,n-1) if(i!=j) a[i][l++]=j;
sort(a[i],a[i]+n-1,[&](int x,int y){return atan2(p[x].y-p[i].y,p[x].x-p[i].x)<atan2(p[y].y-p[i].y,p[y].x-p[i].x);});
rep(j,0,n-2) b[i][a[i][j]]=j;
}
p1.push_back(p1[0]);
rep(i,0,sz(p1)-1) rep(j,0,n-1) if(p[j]==p1[i]) id[i]=j;
rep(i,0,sz(p1)-1) vs[id[i]]=1;
int as=1;
rep(i,0,sz(p1)-2) rep(j,0,n-1){
if((p[j]==p1[i])||(p[j]==p1[i+1])||vs[j]) continue;
int x=b[j][id[i]],y=b[j][id[i+1]];
if(abs(x-y)==1||(x==0&&y==n-2)||(x==n-2&&y==0)) as++;
}
printf("%d\n",as);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6304kb
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: 6360kb
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: 6480kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 6284kb
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: 6208kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
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...