QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#817072 | #9880. Origami Warp | Afterlife# | WA | 0ms | 3572kb | C++20 | 4.7kb | 2024-12-16 20:13:18 | 2024-12-16 20:13:19 |
Judging History
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]