QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696720#7906. Almost ConvexEwiGKeiTWA 0ms3948kbC++142.4kb2024-11-01 00:47:402024-11-01 00:47:42

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 00:47:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3948kb
  • [2024-11-01 00:47:40]
  • 提交

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'