QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696720 | #7906. Almost Convex | EwiGKeiT | WA | 0ms | 3948kb | C++14 | 2.4kb | 2024-11-01 00:47:40 | 2024-11-01 00:47:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL INF=1e9;
const double eps=1e-10;
struct Point
{
LL x,y;
double ang;
int id;
Point operator-(const Point& p) const
{
return {x-p.x,y-p.y};
}
LL operator*(const Point& p) const
{
return x*p.y-y*p.x;
}
} p[2005],ch[2005],q[2005];
int T,n,top,stk[2005],in[2005],m;
LL dis(Point a,Point b)
{
Point d=a-b;
return d.x*d.x+d.y*d.y;
}
void getConvexHull(Point p[],int &n,Point res[],int &m)
{
for (int i=2;i<=n;i++)
if (p[i].y<p[1].y || p[i].y==p[1].y && p[i].x<p[1].x)
swap(p[i],p[1]);
Point ref=p[1];
for (int i=2;i<=n;i++)
p[i].ang=atan2(p[i].y-ref.y,p[i].x-ref.x);
sort(p+2,p+1+n,[ref](Point a,Point b)
{
if (abs(a.ang-b.ang)<eps) return dis(a,ref)<dis(b,ref);
return a.ang<b.ang;
});
stk[top=1]=1;
for (int i=2;i<=n;i++)
{
while (top>=2 && (p[stk[top]]-p[stk[top-1]])*(p[i]-p[stk[top]])<0)
top--;
stk[++top]=i;
}
for (int i=1;i<=n;i++)
in[i]=0;
m=top;
for (int i=1;i<=top;i++)
{
in[stk[i]]=1;
res[i]=p[stk[i]];
}
int tmp=n; n=0;
for (int i=1;i<=tmp;i++)
if (!in[i]) p[++n]=p[i];
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++)
cin >> p[i].x >> p[i].y;
getConvexHull(p,n,ch,m);
for (int i=1;i<=m;i++)
{
q[i]=ch[i];
q[i].id=i;
}
for (int i=1;i<=n;i++)
{
q[m+i]=p[i];
q[m+i].id=-1;
}
cout << n << '\n';
int ans=0;
for (int i=1;i<=n;i++)
{
Point ref=p[i];
for (int j=2;j<=m+n;j++)
if (q[j].x==ref.x && q[j].y==ref.y)
swap(q[j],q[1]);
for (int j=2;j<=m+n;j++)
q[j].ang=atan2(q[j].y-ref.y,q[j].x-ref.x);
sort(q+2,q+1+m+n,[ref](Point a,Point b)
{
if (abs(a.ang-b.ang)<eps) return dis(a,ref)<dis(b,ref);
return a.ang<b.ang;
});
q[m+n+1]=q[2];
for (int j=2;j<=m+n;j++)
if (q[j].id!=-1 && q[j].id%m+1==q[j+1].id)
ans++;
}
cout << ans+1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3948kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
3 9
result:
wrong answer 1st numbers differ - expected: '9', found: '3'