Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <unordered_map>
- #include <unordered_set>
- #include <queue>
- #include <deque>
- #include <cmath>
- #include <numeric>
- #include <algorithm>
- #include <ctime>
- #include <chrono>
- #include <random>
- #include <functional>
- #include <stack>
- //#include <windows.h>
- //void* operator new(size_t size) {
- // if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
- // throw std::bad_alloc{};
- //}
- //void operator delete(void* ptr) {
- // HeapFree(GetProcessHeap(), 0, ptr);
- //}
- using namespace std;
- using ll = long long;
- using db = double;
- using ldb = long double;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vint = vector<int>;
- using vll = vector<ll>;
- using vst = vector<string>;
- #define all(x) x.begin(), x.end()
- #define size(x) int(x.size())
- #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
- #define forp(i, s, f) for(int i = s; i < f; ++i)
- #define form(i, s, f) for(int i = s; i > f; --i)
- #define PB push_back
- #define MP make_pair
- #define F first
- #define S second
- #define elif else if
- #define dprint(x) for (auto now: x) cout << now << ' '
- const int MOD = 1e9 + 7;
- const int MOD2 = 998244353;
- const int INF = 2e9 + 7;
- const ll LINF = 1e18 + 7;
- const double EPS = 1e-9;
- const long double PI = acosl(-1.0);
- bool check_point(pll queen, pll point) {
- return (queen.F == point.F or queen.S == point.S or abs(queen.F - point.F) == abs(queen.S - point.S));
- }
- pii start_queens(vector<pll>& sp) {
- int n = size(sp);
- forp(i, 0, n) {
- forp(j, i + 1, n) {
- if (!check_point(sp[i], sp[j])) {
- return { i, j };
- }
- }
- }
- return { 0, 0 };
- }
- vector<pll> make_intersect(pll a, pll b) {
- vector<pll> ret;
- if (a == b) {
- ret.push_back(a);
- return ret;
- }
- ll x1 = a.first, y1 = a.second;
- ll x2 = b.first, y2 = b.second;
- ll d1 = abs(x1 - x2);
- ll d2 = abs(y1 - y2);
- ret.push_back({ x1, y2 });
- ret.push_back({ x1, y2 + d1 });
- ret.push_back({ x1, y2 - d1 });
- ret.push_back({ x2, y1 });
- ret.push_back({ x2, y1 + d1 });
- ret.push_back({ x2, y1 - d1 });
- ret.push_back({ x1, y2 });
- ret.push_back({ x1 + d2, y2 });
- ret.push_back({ x1 - d2, y2 });
- ret.push_back({ x2, y1 });
- ret.push_back({ x2 + d2, y1 });
- ret.push_back({ x2 - d2, y1 });
- //if ((x1 + y1) % 2 == (x2 + y2) % 2) {
- ll a1 = 1;
- ll a2 = -1;
- ll b1 = y1 - a1 * x1;
- ll b2 = y2 - a2 * x2;
- ll xu1 = (b2 - b1) / (a1 - a2);
- ll yu1 = a1 * xu1 + b1;
- ret.push_back({ xu1, yu1 });
- ll a3 = -1;
- ll a4 = 1;
- ll b3 = y1 - a3 * x1;
- ll b4 = y2 - a4 * x2;
- ll xu2 = (b4 - b3) / (a3 - a4);
- ll yu2 = a3 * xu2 + b3;
- ret.push_back({ xu2, yu2 });
- /* ret.push_back({ (x1 + y2 - y1 + x2) / 2, (y2 + y1 + x2 - x1) / 2 });
- ret.push_back({ (x1 - y2 + y1 + x2) / 2, (y2 + y1 - x2 + x1) / 2 });*/
- //}
- return ret;
- }
- void solve() {
- ll n;
- cin >> n;
- vector<pll> sp(n);
- forp(i, 0, n) cin >> sp[i].F >> sp[i].S;
- if (n == 1) {
- cout << "YES\n" << sp[0].first << ' ' << sp[0].second << '\n';
- return;
- }
- //sort(all(sp));
- pii qs = start_queens(sp);
- pll a = sp[qs.first];
- pll b = sp[qs.second];
- vector<pll> points = make_intersect(a, b);
- for (pll ans : points) {
- bool f = true;
- forp(i, 0, n) {
- if (!check_point(sp[i], ans)) {
- f = false;
- break;
- }
- }
- if (f) {
- cout << "YES\n" << ans.first << ' ' << ans.second << '\n';
- return;
- }
- }
- cout << "NO\n";
- }
- int main() {
- int t;
- cin >> t;
- //t = 1;
- while (t > 0) {
- solve();
- t--;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement