QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371144#7800. Every Queenkevinyang#TL 0ms3848kbC++174.0kb2024-03-30 00:52:162024-03-30 00:52:16

Judging History

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

  • [2024-03-30 00:52:16]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3848kb
  • [2024-03-30 00:52:16]
  • 提交

answer

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
	friend ostream& operator<<(ostream& os, P p) {
		return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<int> P;

template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
	auto d = (e1 - s1).cross(e2 - s2);
	if (d == 0) // if parallel
		return {-(s1.cross(e1, s2) == 0), P(0, 0)};
	auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
	return {1, (s1 * p + e1 * q) / d};
}

bool good(P a, P b){
	int dx = a.x - b.x;
	int dy = a.y - b.y;
	if(dx == 0 || dy == 0 || abs(dx) == abs(dy)){
		return true;
	}
	return false;
}
bool diag(P a, P b){
	int dx = a.x - b.x;
	int dy = a.y - b.y;
	if(dx == 0 || dy == 0)return false;
	return true;
}
vector<P> merge(vector<P> a, vector<P> b){
	set<P>s;
	for(auto nxt: a){
		s.insert(nxt);
	}
	vector<P>ans;
	for(auto nxt: b){
		if(s.find(nxt) == s.end())continue;
		ans.push_back(nxt);
	}
	return ans;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<P>arr(n);
		for(int i = 0; i<n; i++){
			int x,y;
			cin >> x >> y;
			arr[i] = P{x,y};
		}
		if(n==1){
			cout << "YES\n";
			cout << arr[0].x << ' ' << arr[0].y << '\n';
			continue;
		}
		vector<int>dx = {-1,0,1,1};
		vector<int>dy = {-1,-1,-1,0};
		bool found = false;
		for(int iters = 0; iters < 90; iters++){
			int i = 0; int j = 0;
			while(i==j || !good(arr[i], arr[j])){
				i = rng()%n;
				j = rng()%n;
			}
			bool bad = false;
			vector<vector<P>>ans(n);
			bool onepoint = false;
			for(int a = 0; a<n; a++){
				if(a==i || a==j)continue;
				if(diag(arr[i],arr[j])){
					int m = (arr[i].x + arr[i].y)%2;
					m+=2; m%=2;
					int m2 = (arr[a].x + arr[a].y)%2;
					m2+=2; m2%=2;
					if(m!=m2){
						bad = true;
						continue;
					}
				}
				for(int d = 0; d<4; d++){
					P p = P{arr[a].x+dx[d], arr[a].y+dy[d]};
					auto res = lineInter(arr[a],p,arr[i],arr[j]);
					if(res.first != 1)continue;
					ans[a].push_back(res.second);
					onepoint = true;
				}
			}
			if(bad){
				continue;
			}
			if(!onepoint){
				cout << "YES\n";
				cout << arr[i].x << ' ' << arr[i].y << '\n';
				found = true;
				break;
			}
			bool start = false;
			vector<P>cur;
			for(int a = 0; a<n; a++){
				if(!start && ans[a].size()){
					cur = ans[a];
					start = true;
				}
				else if(ans[a].size()){
					cur = merge(cur,ans[a]);
				}
			}
			if(cur.size()){
				cout << "YES\n";
				cout << cur[0].x << ' ' << cur[0].y << '\n';
				found = true;
				break;
			}
		}
		if(found)continue;
		cout << "NO\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
2 2
NO
YES
1 2

result:

ok OK (3 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

1
4
-100000000 -100000000
100000000 -100000000
-100000000 100000000
100000000 100000000

output:

YES
100000000 -100000000

result:

ok OK (1 test case)

Test #3:

score: -100
Time Limit Exceeded

input:

330
3
5 1
-3 -5
-2 2
2
1 4
4 0
4
2 -5
3 -3
-5 4
2 -2
2
-4 1
2 4
1
1 5
4
3 5
-2 3
5 2
-3 -3
5
-3 -4
2 -1
-2 -2
1 0
-1 -5
5
4 -3
-2 -4
2 2
0 -5
-4 -3
4
0 0
-3 -5
0 5
5 0
1
1 -1
5
0 2
3 4
1 4
4 5
5 0
3
-4 -5
-5 -3
5 -5
3
-1 2
-4 -4
-1 5
4
1 1
4 5
-1 0
5 2
1
-3 2
5
5 0
4 1
-3 -5
3 -3
0 0
5
0 1
-5 4
-5 5...

output:


result: