QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883217#9880. Origami WarplichenghanRE 0ms0kbC++171.6kb2025-02-05 15:17:552025-02-05 15:17:55

Judging History

This is the latest submission verdict.

  • [2025-02-05 15:17:55]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-05 15:17:55]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2002;
int gcd(vector<int> v){ return accumulate(v.begin(),v.end(),0,__gcd<int>); }
bool ok=true;
void solve(){
	int n,m;
	scanf("%d",&n);
	bool irr=false,off=false;
	vector<int> ver,hor,cut;
	for(int i=1;i<=n;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int dx=c-a,dy=d-b;
		if((ll)a*d!=(ll)b*c) off=true; 
		if(dx==0) ver.push_back(a);
		else if(dy==0) hor.push_back(b);
		else if(dx==dy) cut.push_back(abs(a-b));
		else if(dx==-dy) cut.push_back(abs(a+b));
		else irr=true;
	}
	scanf("%d",&m);
	if(ok){
		assert(m>=1634);
	}
	function<pair<int,int>(int,int)> sim;
	if(irr){
		if(off){
			sim=[&](int x,int y)->pair<int,int>{return{0,0};};
		}else{
			sim=[&](int x,int y)->pair<int,int>{
				ll res=(ll)x*x+(ll)y*y;
				return {res>>32,res};
			};
		}
	}else if(cut.empty()){
		int gv=gcd(ver),gh=gcd(hor);
		sim=[=](int x,int y)->pair<int,int>{
			if(gv) x%=2*gv;
			if(gh) y%=2*gh;
			return {min(x,2*gv-x),min(y,2*gh-y)};
		};
	}else{
		int gs=__gcd(__gcd(gcd(ver),gcd(hor)),gcd(cut));
		bool add=false;
		for(int i:cut) if(i%(2*gs)==0) add=true;
		sim=[=](int x,int y)->pair<int,int>{
			x%=2*gs; y%=2*gs;
			if(x>gs) x=2*gs-x;
			if(y>gs) y=2*gs-y;
			if(x+y>gs) swap(x,y),x=gs-x,y=gs-y;
			if(add&&x>y) swap(x,y);
			return {x,y};
		};
	}
	while(m--){
		int x,y,z,w;
		scanf("%d%d%d%d",&x,&y,&z,&w);
		x=abs(x); y=abs(y); z=abs(z); w=abs(w);
		puts(sim(x,y)==sim(z,w)?"Yes":"No");
	}
}
int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		solve();
		ok=false;
	}
}

详细

Test #1:

score: 0
Runtime Error

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:


result: