QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314271 | #7906. Almost Convex | taiyangfeng | TL | 1ms | 4192kb | C++20 | 2.4kb | 2024-01-25 15:09:51 | 2024-01-25 15:09:51 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
#define int long long
constexpr double eps=1e-8;
constexpr double PI=acos(-1.0);
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.y-y*b.x;}
double operator*(const Point&b)const{return x*b.x+y*b.y;}
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(double B,Point P){return(Point){(x-P.x)*cos(B)-(y-P.y)*sin(B)+P.x,(x-P.x)*sin(B)+(y-P.y)*cos(B)+P.y};}
};
double dist(Point a,Point b){return sqrt((a-b)*(a-b));}
double len(Point a){return sqrt(a.x*a.x+a.y*a.y);}
Point p[2010],ch[2010];int vis[2010];
void ConvexHull(Point *p,int n,Point *ch){
sort(p,p+n),n=unique(p,p+n)-p;
int m=0,k;
stack<int>ans;
for(int i=0;i<n;++i){
while(m>1&&sgn((ch[m-1]-ch[m-2])^(p[i]-ch[m-1]))<=0)--m,ans.pop();
ch[m++]=p[i],ans.push(i);
}k=m;
for(int i=n-2;i>=0;--i){
while(m>k&&sgn((ch[m-1]-ch[m-2])^(p[i]-ch[m-1]))<=0)--m,ans.pop();
ch[m++]=p[i],ans.push(i);
}if(n>1)--m,ans.pop();
while(!ans.empty())vis[ans.top()]=1,ans.pop();
}
unordered_map<int,int>mp;
inline int getpoint(double x,double y){return (x+1000001)*2000001+y;}
inline int getpoint(Point i){return getpoint(i.x,i.y);}
Point C,P[2010];
bool cmp(Point a,Point b){
a=a-C,b=b-C;
if(atan2(a.y,a.x)!=atan2(b.y,b.x))
return atan2(a.y,a.x)<atan2(b.y,b.x);
else return a.x<b.x;
}
signed main(){
int n,ans=0;cin>>n;
for(int i=0;i<n;++i)cin>>p[i].x>>p[i].y;
ConvexHull(p,n,ch);
for(int i=0;i<n;++i)if(vis[i])mp[getpoint(p[i])]=1;
for(int i=0;i<n;++i)if(!mp.count(getpoint(p[i]))){
int cnt=0;for(int j=0;j<n;++j)if(j!=i)P[cnt++]=p[j];
C=p[i];sort(P,P+cnt,cmp);
//for(int j=0;j<cnt;++j)cout<<P[j].x<<' '<<P[j].y<<endl;
//cout<<endl;
for(int j=0;j<cnt;++j)if(mp.count(getpoint(P[j]))&&mp.count(getpoint(P[(j+1)%cnt])))
++ans;//cout<<p[i].x<<' '<<p[i].y<<' '<<P[j].x<<' '<<P[j].y<<' '<<P[(j+1)%cnt].x<<' '<<P[(j+1)%cnt].y<<endl;
}
cout<<ans+1<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4088kb
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: 4192kb
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: 3840kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4104kb
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: 3900kb
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...