QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364561 | #7906. Almost Convex | Zhou_JK | TL | 1ms | 4044kb | C++23 | 2.6kb | 2024-03-24 15:18:14 | 2024-03-24 15:18:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
class Point
{
public:
int x,y;
Point(int _x=0,int _y=0):x(_x),y(_y){}
friend long long cross(const Point &a,const Point &b)
{
return (long long)a.x*b.y-(long long)a.y*b.x;
}
friend Point operator - (const Point &a,const Point &b)
{
return Point(a.x-b.x,a.y-b.y);
}
int quadrant()const
{
if(x>0&&y>=0) return 1;
else if(x<=0&&y>0) return 2;
else if(x<0&&y<=0) return 3;
else if(x>=0&&y<0) return 4;
else return 0;
}
double angle()const
{
return atan2(y,x);
}
};
bool cmp_polar_angle(const Point &a,const Point &b)
{
int x=a.quadrant(),y=b.quadrant();
if(x!=y) return x<y;
else return cross(a,b)>0;
}
vector<int> convex_hull(const vector<Point> &p)
{
int n=p.size();
if(n<=2)
{
vector<int>res(n,0);
for(int i=0;i<n;i++)
res[i]=i;
return res;
}
vector<int>id(n);
iota(id.begin(),id.end(),0);
sort(id.begin(),id.end(),[=](const int &a,const int &b){return p[a].x==p[b].x?p[a].y<p[b].y:p[a].x<p[b].x;});
vector<int>stk;
int top=0;
for(int i=0;i<n;i++)
{
while(top>=2&&cross(p[stk[top-1]]-p[stk[top-2]],p[id[i]]-p[stk[top-1]])<=0) stk.pop_back(),top--;
stk.emplace_back(id[i]),top++;
}
int tmp=top;
for(int i=n-2;i>=0;i--)
{
while(top>tmp&&cross(p[stk[top-1]]-p[stk[top-2]],p[id[i]]-p[stk[top-1]])<=0) stk.pop_back(),top--;
stk.emplace_back(id[i]),top++;
}
stk.pop_back(),top--;
vector<int> hull;
for(int i=0;i<top;i++)
hull.emplace_back(stk[i]);
return hull;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
cin>>n;
vector<Point>p(n);
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
p[i]=Point(x,y);
}
vector<int>q=convex_hull(p);
vector<int>vis(n,0);
for(int u:q)
vis[u]=true;
vector<int>pp(n);
iota(pp.begin(),pp.end(),0);
vector<double>dp(n);
int ans=1;
for(int x=0;x<n;x++)
if(!vis[x])
{
for(int i=0;i<n;i++)
{
if(i==x) dp[i]=-1e9;
else dp[i]=(p[i]-p[x]).angle();
}
sort(pp.begin(),pp.end(),[=](const int &a,const int &b){return dp[a]<dp[b];});
for(int i=1;i<n;i++)
{
int j=i+1;
if(j>=n) j=1;
if(vis[pp[i]]&&vis[pp[j]]) ans++;
}
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3768kb
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: 4044kb
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: 3580kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4004kb
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: 3756kb
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...