QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#817072#9880. Origami WarpAfterlife#WA 0ms3572kbC++204.7kb2024-12-16 20:13:182024-12-16 20:13:19

Judging History

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

  • [2024-12-16 20:13:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-12-16 20:13:18]
  • 提交

answer

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

#define int long long

struct P {
    int x,y;

    int len2()
    {
        return x*x+y*y;
    }

    void norm(int X,int Y)
    {
        if(X!=1e9)
            x=(x%X+X)%X;
        else
            x=abs(x);
        if(Y!=1e9)
            y=(y%Y+Y)%Y;
        else
            y=abs(y);
    }
};

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

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

struct L {
    P u,v;
    int cut()
    {
        P d=u-v;
        if(d.x==0)
            return u.x;
        else if(d.y==0)
            return u.y;
        else if(d.x==d.y)
            return u.y-u.x;
        else if(d.x==-d.y)
            return u.y+u.x;
        else
            assert(0);
    }
    P sym(P a)
    {
        P d=u-v;
        if(d.x==0)
            return {u.x*2-a.x,a.y};
        else if(d.y==0)
            return {a.x,u.y*2-a.y};
        else if(d.x==d.y)
        {
            int e=u.y-u.x;
            return {a.y-e,a.x+e};
        }
        else if(d.x==-d.y)
        {
            int e=u.y+u.x;
            return {e-a.y,e-a.x};
        }
        else
            assert(0);
    }

};

bool on(P u,L a)
{
    return det(a.u-u,a.v-a.u)==0;
}

int T,n,Q;

void out(int ver)
{
    cout<<(ver?"Yes":"No")<<"\n";
}

bool operator <(const P &a,const P &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

int br(P u,vector<L> &uL,int MX,int MY,P e)
{
    queue<P> q;
    u.norm(MX,MY);
    q.push(u);
    e.norm(MX,MY);
    set<P> ret({u});
    while(!q.empty())
    {
        if(u.x==e.x&&u.y==e.y)
            return 1;
        auto p=q.front();
        q.pop();
        for(auto l:uL)
        {
            P v=l.sym(p);
            v.norm(MX,MY);
            if(!ret.count(v))
                ret.insert(v),q.push(v);                
        }
    }
    return 0;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        vector<L> lines(n);
        for(auto &[u,v]:lines)
            cin>>u.x>>u.y>>v.x>>v.y;
        P O={0,0};
        int allpassO=1;
        int strange=0;
        vector<L> x0,y0,xx,nx;
        for(auto l:lines)
        {
            if(!on(O,l))
                allpassO=0;
            P dir=l.u-l.v;
            if(dir.x!=0&&dir.y!=0&&abs(dir.x)!=abs(dir.y))
                strange=1;
            if(dir.x==0)
                x0.push_back(l);
            if(dir.y==0)
                y0.push_back(l);
            if(dir.x==dir.y)
                xx.push_back(l);
            if(dir.x==-dir.y)
                nx.push_back(l);
        }
        int gx0=0,gy0=0,gxx=0,gnx=0;
        for(int i=0;i<x0.size();i++)
            gx0=__gcd(gx0,abs(x0[i].cut()));
        for(int i=0;i<y0.size();i++)
            gy0=__gcd(gy0,abs(y0[i].cut()));
        for(int i=0;i<xx.size();i++)
            gxx=__gcd(gxx,abs(xx[i].cut()));
        for(int i=0;i<nx.size();i++)
            gnx=__gcd(gnx,abs(nx[i].cut()));
        int GX=0,GY=0;
        GX=gx0,GY=gy0;
        if(xx.size()||nx.size())
            GX=__gcd(GX,GY),GX=__gcd(GX,gxx),GX=__gcd(GX,gnx),GY=GX;
        int MX=0,MY=0;
        vector<L> uL;
        MX=GX*4,MY=GY*4;
        if(!MX)
            MX=1e9;
        if(!MY)
            MY=1e9;
        map<int,int> vis;
        for(int i=0;i<x0.size();i++)
            if(!vis[abs(x0[i].cut())%MX])
                uL.push_back(x0[i]),vis[abs(x0[i].cut())%MX]=1;
        vis.clear();
        for(int i=0;i<y0.size();i++)
            if(!vis[abs(y0[i].cut())%MY])
                uL.push_back(y0[i]),vis[abs(y0[i].cut())%MY]=1;
        vis.clear();
        for(int i=0;i<xx.size();i++)
            if(!vis[abs(xx[i].cut())%MX])
                uL.push_back(xx[i]),vis[abs(xx[i].cut())%MX]=1;
        vis.clear();
        for(int i=0;i<nx.size();i++)
            if(!vis[abs(nx[i].cut())%MX])
                uL.push_back(nx[i]),vis[abs(nx[i].cut())%MX]=1;
        cin>>Q;
        while(Q--)
        {
            P u,v;
            cin>>u.x>>u.y>>v.x>>v.y;
            if(allpassO)
            {
                if(strange)
                    out(u.len2()==v.len2());
                else
                {
                    //brute force
                    auto ans=br(u,uL,MX,MY,v);
                    out(ans);
                }
            }
            else
            {
                if(strange)
                    out(1);
                else
                {
                    //brute force
                    auto ans=br(u,uL,MX,MY,v);
                    out(ans);
                }
            }
        }
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3572kb

input:

2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3

output:

No
No
No
Yes
Yes
Yes

result:

wrong answer expected YES, found NO [1st token]