QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847592#9880. Origami WarpWuyanruWA 54ms4016kbC++144.2kb2025-01-08 07:47:182025-01-08 07:47:19

Judging History

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

  • [2025-01-08 07:47:19]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:4016kb
  • [2025-01-08 07:47:18]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll a[2005],b[2005],c[2005],d[2005];
ll A[2005],B[2005],C[2005],D[2005];
int n,m;
inline bool check()
{
    for(int i=1;i<=n;i++)
    {
        if(a[i]==c[i]||b[i]==d[i]) continue;
        ll X=abs(a[i]-c[i]),Y=abs(b[i]-d[i]);
        if(X!=Y) return true;
    }
    return false;
}
inline ll P(ll a){ return a*a;}
inline bool checkO()//所有直线都过原点
{
    for(int i=1;i<=n;i++) if(b[i]*c[i]!=d[i]*a[i]) return false;
    return true;
}
inline bool check13()
{
    for(int i=1;i<=n;i++) if(a[i]!=c[i]&&b[i]!=d[i]) return true;
    return false;
}
inline ll gcd(ll a,ll b)
{
    if(!a||!b) return a|b;
    a=abs(a),b=abs(b);
    ll r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
inline bool MOD(ll a,ll mod)
{
    return (a%mod+mod)%mod;
}
inline bool check(ll a,ll b,ll g)
{
    if(!g) return abs(a)==abs(b);
    if(MOD(a,2*g)==MOD(b,2*g)) return true;
    return MOD(-a,2*g)==MOD(b,2*g);
}
inline void solve()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
    m=read();
    for(int i=1;i<=m;i++) A[i]=read(),B[i]=read(),C[i]=read(),D[i]=read();
    //存在好的交点
    if(check())
    {
        bool f=checkO();
        for(int i=1;i<=m;i++)
        {
            if(!f) printf("Yes\n");//存在不为原点的好的交点
            else if(P(A[i])+P(B[i])==P(C[i])+P(D[i])) printf("Yes\n");
            else printf("No\n");
        }
        return ;
    }
    //不存在好的交点
    if(checkO())//所有点都过原点
    {
        int f1=0,f3=0;
        for(int i=1;i<=n;i++) if(a[i]!=c[i])
        {
            ll k=(d[i]-b[i])/(c[i]-a[i]);
            if(k==1) f1=1;else f3=1;
        }
        for(int i=1;i<=m;i++)
        {
            bool ok=0;
            for(int o1=0;o1<=f1;o1++) for(int o3=0;o3<=f3;o3++)
            {
                int X=A[i],Y=B[i];
                if(o1) swap(X,Y);
                if(o3) swap(X,Y),X=-X,Y=-Y;
                if(abs(X)==abs(C[i])&&abs(Y)==abs(D[i])) ok=1;
            }
            if(ok) printf("Yes\n");
            else printf("No\n");
        }
        return ;
    }
    //不存在1或3型直线
    if(!check13())
    {
        ll gx=0,gy=0;
        for(int i=3;i<=n;i++)
        {
            if(a[i]==c[i]) gx=gcd(gx,a[i]);
            else gy=gcd(gy,b[i]);
        }
        for(int i=1;i<=m;i++) if(check(A[i],C[i],gx)&&check(B[i],D[i],gy)) printf("Yes\n");
            else printf("No\n");
        return ;
    }
    //存在不过原点的1/3型直线
    //按照与x轴的交点,存储所有1型直线
    vc<ll>X;ll g=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==c[i]||b[i]==d[i]) continue;
        ll k=(d[i]-b[i])/(c[i]-a[i]);
        if(k==1) X.push_back(a[i]-c[i]);
        else X.push_back(a[i]+c[i]);
    }
    assert(X.size());
    for(int i=1;i<=n;i++)
    {
        if(a[i]==c[i]) g=gcd(g,a[i]);
        else g=gcd(g,b[i]-X[0]);
    }
    ll W=0;
    for(unsigned i=1;i<X.size();i++) W=gcd(W,X[i]-X[0]);
    W+=X[0];
    for(int i=1;i<=m;i++)
    {
        bool ok=0;
        for(int o1=0;o1<2;o1++) for(int o3=0;o3<2;o3++)
        {
            ll nx=A[i],ny=B[i];
            if(o1) swap(nx,ny),nx+=X[0],ny-=X[0];
            if(o3) swap(nx,ny),nx=W-nx,ny=W-ny;
            if(check(nx,C[i],g)&&check(ny,D[i],g)) ok=1;
        }
        if(ok) printf("Yes\n");
        else printf("No\n");
    }
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

Yes
Yes
No
Yes
Yes
Yes

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: 0
Accepted
time: 3ms
memory: 3792kb

input:

10
550
0 0 1 0
0 0 0 1
1070451 -76747419 -475756 34109964
39212129 -40187389 32082651 -32880591
-42770825 49053520 -51324990 58864224
301020 -10533714 602040 -21067428
-55137616 74952624 -24122707 32791773
1629975 -29851650 -478126 8756484
80523100 20960200 -77302176 -20121792
-64028006 61179727 -18...

output:

Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Ye...

result:

ok 12244 token(s): yes count is 6128, no count is 6116

Test #3:

score: 0
Accepted
time: 54ms
memory: 3856kb

input:

100
2000
0 0 1 0
0 0 0 1
-84998108 27087723 -78459792 25004052
-63732795 -93286980 29741971 43533924
88160702 10753904 -94457895 -11522040
-57759240 -99131840 25991658 44609328
-35408095 31386545 -92061047 81605017
21178080 37382229 32943680 58150134
-57187533 84956404 -17596164 26140432
38432164 17...

output:

No
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
No
Yes
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
N...

result:

ok 200000 token(s): yes count is 100141, no count is 99859

Test #4:

score: -100
Wrong Answer
time: 43ms
memory: 4016kb

input:

90
1025
0 0 1 0
0 0 0 1
-8716657 -748858 12990792 -22456307
-13593063 -23283552 -46628353 -23283552
93002789 28574481 93002789 78693002
-16042487 47828662 -30013237 61799412
43359811 68260568 43359811 -75987953
-94388305 52022201 -94388305 8537759
-6363687 -1383673 -6363687 -20211179
-29739675 -2602...

output:

Yes
No
No
No
Yes
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
N...

result:

wrong answer expected NO, found YES [1634th token]