QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#592472#7081. Cut the PlaneAfterlifeWA 0ms3616kbC++209.0kb2024-09-26 22:48:442024-09-26 22:48:45

Judging History

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

  • [2024-09-26 22:48:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-09-26 22:48:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e2+1e1+7,L=12;

struct P{
    int x,y;
    P(int _x=0,int _y=0){x=_x,y=_y;}
};

P operator *(const P &a,const int &b)
{
    return {a.x*b,a.y*b};
}

P operator -(const P &a,const P &b)
{
    return {a.x-b.x,a.y-b.y};
}

P operator +(const P &a,const P &b)
{
    return {a.x+b.x,a.y+b.y};
}

int T;

int sgn(int x)
{
    return x<-0?-1:(x>0);
}

int det(P a,P b)
{
    return a.x*b.y-a.y*b.x;
}

int dot(P a,P b)
{
    return a.x*b.x+a.y*b.y;
}

int in_seg(P a,P b,P c)
{
    return sgn(det(b-a,c-a))==0&&sgn(dot(a-c,b-c))<=0;
}

int segment_intersection(P a,P b,P c,P d)
{
    if(sgn(det(b-a,c-a))*sgn(det(b-a,d-a))==-1&&sgn(det(d-c,a-c))*sgn(det(d-c,b-c))==-1)
        return 1;
    if(in_seg(a,b,d)||in_seg(a,b,c)||in_seg(c,d,a)||in_seg(c,d,b))
        return 1;
    return 0;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        // n=100;
        vector<P>p(n);
        for(auto &[x,y]:p)
        {
            // x=rand()%10000,y=rand()%10000;
            // x*=2,y*=2;
            cin>>x>>y;
        }
        if(n==1)
        {
            cout<<(int)1e8<<" "<<(int)1e8<<" "<<(int)1e8+1<<" "<<(int)1e8<<"\n";
            continue;
        }
        sort(p.begin(),p.end(),[&](const P &a,const P &b){
            if(a.y!=b.y)
                return a.y<b.y;
            return a.x>b.x;
        });
        int h=n/2;
        P m=(p[h-1]+p[h]);
        m.x/=2,m.y/=2;
        vector<pair<P,P> >ans;
        P A=m+P(1e8,0);
        P B=m+P(-1e8,0);
        P mab,mcd;
        while(1)
        {
            mab=A,mcd=B;
            mab.x+=rand()%L-L/2;
            mab.y+=rand()%L-L/2;
            mcd.x+=rand()%L-L/2;
            mcd.y+=rand()%L-L/2;
            int ok=1;
            for(int i=0;i<n;i++)
            {
                if(in_seg(mab,mcd,p[i]))
                {
                    ok=0;
                    break;
                }
            }
            for(int i=0;i<h;i++)
            {
                if(!ok)
                    break;
                for(int j=h;j<n;j++)
                    if(!segment_intersection(p[i],p[j],mab,mcd))
                    {
                        ok=0;
                        break;
                    }
            }
            if(ok)
                break;
        }
        ans.push_back({mab,mcd});
        sort(p.begin(),p.begin()+h,[&](const P &a,const P &b){
            if(a.x!=b.x)
                return a.x<b.x;
            return a.y<b.y;
        });
        sort(p.begin()+h,p.begin()+n,[&](const P &a,const P &b){
            if(a.x!=b.x)
                return a.x<b.x;
            return a.y<b.y;
        });
        // int u=0,v=h;
        using pii=pair<int,int>;
        queue<pii> q1,q2;
        for(int i=0;i<h;i++)
            for(int j=i+1;j<h;j++)
                q1.push({i,j});
        for(int i=h;i<n;i++)
            for(int j=i+1;j<n;j++)
                q2.push({i,j});
        while(!q1.empty()&&!q2.empty())
        {
            while(q1.size())
            {
                auto [a,b]=q1.front();
                int ok=0;
                for(auto [u,v]:ans)
                    if(segment_intersection(p[a],p[b],u,v))
                    {
                        ok=1;
                        break;
                    }
                if(ok)
                    q1.pop();
                else
                    break;
            }
            
            while(q2.size())
            {
                auto [a,b]=q2.front();
                int ok=0;
                for(auto [u,v]:ans)
                    if(segment_intersection(p[a],p[b],u,v))
                    {
                        ok=1;
                        break;
                    }
                if(ok)
                    q2.pop();
                else
                    break;
            }
            if(!q1.size()||!q2.size())
                break;
            auto [ia,ib]=q1.front();
            auto [ic,id]=q2.front();
            q1.pop(),q2.pop();
            P a=p[ia],b=p[ib],c=p[ic],d=p[id];
            P mab=a+b;
            mab.x/=2,mab.y/=2;
            P mcd=c+d;
            mcd.x/=2,mcd.y/=2;
            P dir=a+b-c-d;
            mab=mab+dir*50000;
            mcd=mcd-dir*50000;
            P A=mab,B=mcd;
            int lim=10,ok=1;
            while(lim--)
            {
                mab=A;
                mcd=B;
                mab.x+=rand()%L-L/2;
                mcd.x+=rand()%L-L/2;
                mab.y+=rand()%L-L/2;
                mcd.y+=rand()%L-L/2;
                ok=1;
                for(int i=0;i<n;i++)
                {
                    if(!ok)
                        break;
                    if(in_seg(mab,mcd,p[i]))
                        ok=0;
                }
                if(!segment_intersection(mab,mcd,a,b)||!segment_intersection(mab,mcd,c,d))
                    ok=0;
                if(ok)
                    break;
            }
            if(!ok)
            {
                q1.push({ia,ib});
                q2.push({ic,id});
            }
            ans.push_back({mab,mcd});
        }
        while(q1.size())
        {
            while(q1.size())
            {
                auto [a,b]=q1.front();
                int ok=0;
                for(auto [u,v]:ans)
                    if(segment_intersection(p[a],p[b],u,v))
                    {
                        ok=1;
                        break;
                    }
                if(ok)
                    q1.pop();
                else
                    break;
            }
            if(!q1.size())
                break;
            P a=p[q1.front().first],b=p[q1.front().second];
            q1.pop();
            P m=(a+b);
            m.x/=2,m.y/=2;
            P A=P(m.x,m.y+1e8),B=P(m.x,m.y-1e8);
            P mab,mcd;
            while(1)
            {
                mab=A;
                mcd=B;
                mab.x+=rand()%L-L/2;
                mcd.x+=rand()%L-L/2;
                mab.y+=rand()%L-L/2;
                mcd.y+=rand()%L-L/2;
                int ok=1;
                for(int i=0;i<n;i++)
                {
                    if(!ok)
                        break;
                    if(in_seg(mab,mcd,p[i]))
                        ok=0;
                }
                if(!segment_intersection(mab,mcd,a,b))
                    ok=0;
                if(ok)
                    break;

            }
            ans.push_back({mab,mcd});

        }
        while(q2.size())
        {
            while(q2.size())
            {
                auto [a,b]=q2.front();
                int ok=0;
                for(auto [u,v]:ans)
                    if(segment_intersection(p[a],p[b],u,v))
                    {
                        ok=1;
                        break;
                    }
                if(ok)
                    q2.pop();
                else
                    break;
            }
            if(!q2.size())
                break;
            P a=p[q2.front().first],b=p[q2.front().second];
            q2.pop();
            P m=(a+b);
            m.x/=2,m.y/=2;
            P A=P(m.x,m.y+1e8),B=P(m.x,m.y-1e8);
            
            P mab,mcd;
            while(1)
            {
                mab=A;
                mcd=B;
                mab.x+=rand()%L-L/2;
                mcd.x+=rand()%L-L/2;
                mab.y+=rand()%L-L/2;
                mcd.y+=rand()%L-L/2;
                int ok=1;
                for(int i=0;i<n;i++)
                {
                    if(!ok)
                        break;
                    if(in_seg(mab,mcd,p[i]))
                        ok=0;
                }
                if(!segment_intersection(mab,mcd,a,b))
                    ok=0;
                if(ok)
                    break;

            }
            ans.push_back({mab,mcd});

        }
        for(auto &[a,b]:ans)
        {
            cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<"\n";
        }
        int z=1e8;
        int tot=(n+1)/2;
        while(ans.size()<tot)
        {
            cout<<(int)z<<" "<<(int)z<<" "<<(int)z+1<<" "<<(int)z<<"\n";
            z++;
            tot--;
        }

        // int ok=1;
        // // ok&=ans.size()==(n+1)/2;
        // for(int i=0;i<n;i++)
        // {
        //     for(auto [u,v]:ans)
        //     {
        //         if(in_seg(u,v,p[i]))
        //             ok=0;
        //     }
        //     for(int j=i+1;j<n;j++)
        //     {
        //         int flag=0;
        //         for(auto [u,v]:ans)
        //             if(segment_intersection(p[i],p[j],u,v))
        //                 flag=1;
        //         ok&=flag;
        //     }
        // }
        // cout<<ok<<endl;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

input:

2
3
0 0
2 1
4 0
4
0 1
1 0
2 1
1 2

output:

99999998 4 -99999995 -4
1 99999995 3 -100000003
99999999 6 -99999996 -4
100006 -99996 -100005 99999

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

4
2
0 0
3 0
3
0 0
3 0
3 3
4
0 0
3 0
3 3
0 3
4
0 0
3 0
1 1
0 3

output:

99999997 4 -99999996 -4
99999999 4 -99999995 -4
1 99999995 1 -100000005
99999996 3 -99999999 1
2 -299998 1 300006
100000000 3 -99999998 -2
99995 -200005 -100001 199996
100000 -200000 -100000 200006

result:

wrong answer In case 4, there exist two points lie in the same piece.