QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627211#7800. Every QueenIllusionaryDominance#Compile Error//C++202.8kb2024-10-10 15:12:492024-10-10 15:12:50

Judging History

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

  • [2024-10-10 15:12:50]
  • 评测
  • [2024-10-10 15:12:49]
  • 提交

answer

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

const int N = 1e5 + 10;

const long long dA[] = {1, 0, 1, 1};
const long long dB[] = {0, 1, 1, -1};

struct Point{
	long long x, y;
}P[N];
int n;

struct Line{long long A, B, C;};

bool check_on_line(Point p, Line l){return abs(l.A * p.x + l.B * p.y + l.C) == 0;}
bool legal_point(Point p){return abs(p.x) <= 1e9 && abs(p.y) <= 1e9;}
Line calc_line(Point p, int fx){return (Line){dA[fx], dB[fx], - dA[fx] * p.x - dB[fx] * p.y};}
Point cross_line(Line l1, Line l2){
	if(l1.A == l2.A && l1.B == l2.B) return (Point){2e9, 2e9};
	if(l1.A == 0) swap(l1, l2);
	if(l2.A){l2.A -= l1.A, l2.B -= l1.B, l2.C -= l1.C;}
	long long y = -l2.C / l2.B;
	if(l2.C % l2.B) y = 2e9;
	long long x = (-l1.B * y - l1.C) / l1.A;
	return (Point){x, y};
}


map<double, int>ids;

bool check(Point p){
	for (int i = 1; i <= n; ++ i){
		int flag = 0;
		for (int fx = 0; fx < 4; ++ fx) flag |= check_on_line(p, (Line){dA[fx], dB[fx], - dA[fx] * P[i].x - dB[fx] * P[i].y});
		if(flag == 0) return 0;
	}
	return 1;
}

pair<int, Point> two_point_check(Point p1, Point p2){
	for (int fx1 = 0; fx1 < 4; ++ fx1)
		for (int fx2 = 0; fx2 < 4; ++ fx2){
			if(fx1 == fx2) continue;
			Point p = cross_line((Line){dA[fx1], dB[fx1], - dA[fx1] * p1.x - dB[fx1] * p1.y}, (Line){dA[fx2], dB[fx2], - dA[fx2] * p2.x - dB[fx2] * p2.y});
			if(legal_point(p) && check(p)) return make_pair(1, p);
		}
	return make_pair(-1, (Point){0, 0});
}

pair<int, Point> find(double A, double B){
	ids.clear();
	
	for (int i2 = 1; i2 <= n; ++ i2){
		if(ids[A * P[i2].x + B * P[i2].y]){
			int i1 = ids[A * P[i2].x + B * P[i2].y];
			Line l = (Line){A, B, - A * P[i2].x - B * P[i2].y};
			for (int i = 1; i <= n; ++ i)
				if (!check_on_line(P[i], l)){
					for (int fx = 0; fx < 4; ++ fx){
						Point p = cross_line(l, (Line){dA[fx], dB[fx], - dA[fx] * P[i].x - dB[fx] * P[i].y});
						if(legal_point(p) && check(p)) return make_pair(1, p);
					}
					break;
				}
			pair<int, Point> re = two_point_check(P[i1], P[i2]);
			return re;
		}
		ids[A * P[i2].x + B * P[i2].y] = i2;
	}
	return make_pair(0, (Point){0, 0});
}

void print(pair<int, Point> ans){
	cout << (ans.first == 1 ? "Yes\n" : "No\n");
	if(ans.first == 1) cout << ans.second.x << " " << ans.second.y << "\n";
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T --){
		cin >> n;
		
		for (int i = 1; i <= n; ++ i) cin >> P[i].x >> P[i].y;
		
		if(n == 1) {print(make_pair(1, P[1])); continue;}
		
		
		int flag = 0;
		
		for (int i = 0; i < 4; ++ i){
			pair<int, Point> ans = find(dA[i], dB[i]);
			if(ans.first != 0){print(ans); flag = 1; break;}
		}
		
		if(flag) continue;
		
		pair<int, Point> ans = two_point_check(P[1], P[2]);
		
		print(ans);
		
	}
}

Details

answer.code: In function ‘Point cross_line(Line, Line)’:
answer.code:20:57: error: narrowing conversion of ‘2.0e+9’ from ‘double’ to ‘long long int’ [-Wnarrowing]
   20 |         if(l1.A == l2.A && l1.B == l2.B) return (Point){2e9, 2e9};
      |                                                         ^~~
answer.code: In function ‘std::pair<int, Point> find(double, double)’:
answer.code:57:41: warning: narrowing conversion of ‘A’ from ‘double’ to ‘long long int’ [-Wnarrowing]
   57 |                         Line l = (Line){A, B, - A * P[i2].x - B * P[i2].y};
      |                                         ^
answer.code:57:44: warning: narrowing conversion of ‘B’ from ‘double’ to ‘long long int’ [-Wnarrowing]
   57 |                         Line l = (Line){A, B, - A * P[i2].x - B * P[i2].y};
      |                                            ^
answer.code:57:61: warning: narrowing conversion of ‘(((- A) * (double)P[i2].Point::x) - (B * (double)P[i2].Point::y))’ from ‘double’ to ‘long long int’ [-Wnarrowing]
   57 |                         Line l = (Line){A, B, - A * P[i2].x - B * P[i2].y};
      |                                               ~~~~~~~~~~~~~~^~~~~~~~~~~~~