QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371160#7800. Every Queenkevinyang#WA 1ms3824kbC++174.1kb2024-03-30 01:04:502024-03-30 01:04:51

Judging History

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

  • [2024-03-30 01:04:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-03-30 01:04:50]
  • 提交

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 j = 0; j<2; j++){
			for(int dir = 0; dir<4; dir++){
				if(found)break;
				P p = P{arr[j].x+dx[dir], arr[j].y+dy[dir]};
				vector<vector<P>>ans(n);
				bool bad = false;
				bool onepoint = false;
				for(int i = 0; i<n; i++){
					if(i==j)continue;
					if(diag(arr[j],p)){
						int m = (arr[j].x + arr[j].y)%2;
						m+=2; m%=2;
						int m2 = (arr[i].x + arr[i].y)%2;
						m2+=2; m2%=2;
						if(m!=m2){
							bad = true;
							continue;
						}
					}
					if((arr[j]-p).cross(arr[i]-arr[j]) == 0)continue;
						for(int d = 0; d<4; d++){
						P p2 = P{arr[i].x+dx[d], arr[i].y+dy[d]};
						auto res = lineInter(arr[j],p,arr[i],p2);
						if(res.first != 1)continue;
						ans[i].push_back(res.second);
						onepoint = true;
					}
				}
				if(bad){
					continue;
				}
				if(!onepoint){
					cout << "YES\n";
					cout << arr[j].x << ' ' << arr[j].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)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: 1ms
memory: 3676kb

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
1 1
NO
YES
1 2

result:

ok OK (3 test cases)

Test #2:

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

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
Wrong Answer
time: 1ms
memory: 3660kb

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:

YES
-2 -6
YES
1 -3
YES
2 -3
YES
-4 -2
YES
1 5
NO
NO
NO
YES
0 -5
YES
1 -1
NO
YES
-7 -5
YES
-1 -1
YES
1 2
YES
-3 2
NO
YES
-5 -4
YES
-3 -3
YES
-5 -3
YES
-2 0
NO
YES
2 0
YES
-1 -2
YES
5 1
YES
0 -1
YES
1 5
YES
-5 -2
NO
NO
YES
5 5
NO
YES
1 -7
YES
3 5
YES
-1 -1
YES
-5 1
NO
NO
YES
2 4
YES
2 4
YES
1 -4
YES
-...

result:

wrong answer Jury found solution, but participant did not (test case 28)