Advertisement
cyberjab

E. Every Queen 2023

Oct 3rd, 2024 (edited)
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.04 KB | Software | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13. #include <queue>
  14. #include <deque>
  15. #include <cmath>
  16. #include <numeric>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <chrono>
  20. #include <random>
  21. #include <functional>
  22. #include <stack>
  23. //#include <windows.h>
  24. //void* operator new(size_t size) {
  25. //    if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
  26. //    throw std::bad_alloc{};
  27. //}
  28. //void operator delete(void* ptr) {
  29. //    HeapFree(GetProcessHeap(), 0, ptr);
  30. //}
  31.  
  32. using namespace std;
  33. using ll = long long;
  34. using db = double;
  35. using ldb = long double;
  36. using pii = pair<int, int>;
  37. using pll = pair<ll, ll>;
  38. using vint = vector<int>;
  39. using vll = vector<ll>;
  40. using vst = vector<string>;
  41. #define all(x) x.begin(), x.end()
  42. #define size(x) int(x.size())
  43. #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
  44. #define forp(i, s, f) for(int i = s; i < f; ++i)
  45. #define form(i, s, f) for(int i = s; i > f; --i)
  46. #define PB push_back
  47. #define MP make_pair
  48. #define F first
  49. #define S second
  50. #define elif else if
  51. #define dprint(x) for (auto now: x) cout << now << ' '
  52.  
  53. const int MOD = 1e9 + 7;
  54. const int MOD2 = 998244353;
  55. const int INF = 2e9 + 7;
  56. const ll LINF = 1e18 + 7;
  57. const double EPS = 1e-9;
  58. const long double PI = acosl(-1.0);
  59.  
  60. bool check_point(pll queen, pll point) {
  61.     return (queen.F == point.F or queen.S == point.S or abs(queen.F - point.F) == abs(queen.S - point.S));
  62. }
  63.  
  64. pii start_queens(vector<pll>& sp) {
  65.     int n = size(sp);
  66.     forp(i, 0, n) {
  67.         forp(j, i + 1, n) {
  68.             if (!check_point(sp[i], sp[j])) {
  69.                 return { i, j };
  70.             }
  71.         }
  72.     }
  73.     return { 0, 0 };
  74. }
  75.  
  76. vector<pll> make_intersect(pll a, pll b) {
  77.     vector<pll> ret;
  78.     if (a == b) {
  79.         ret.push_back(a);
  80.         return ret;
  81.     }
  82.     ll x1 = a.first, y1 = a.second;
  83.     ll x2 = b.first, y2 = b.second;
  84.     ll d1 = abs(x1 - x2);
  85.     ll d2 = abs(y1 - y2);
  86.  
  87.     ret.push_back({ x1, y2 });
  88.     ret.push_back({ x1, y2 + d1 });
  89.     ret.push_back({ x1, y2 - d1 });
  90.  
  91.     ret.push_back({ x2, y1 });
  92.     ret.push_back({ x2, y1 + d1 });
  93.     ret.push_back({ x2, y1 - d1 });
  94.  
  95.     ret.push_back({ x1, y2 });
  96.     ret.push_back({ x1 + d2, y2 });
  97.     ret.push_back({ x1 - d2, y2 });
  98.  
  99.     ret.push_back({ x2, y1 });
  100.     ret.push_back({ x2 + d2, y1 });
  101.     ret.push_back({ x2 - d2, y1 });
  102.  
  103.     //if ((x1 + y1) % 2 == (x2 + y2) % 2) {
  104.     ll a1 = 1;
  105.     ll a2 = -1;
  106.     ll b1 = y1 - a1 * x1;
  107.     ll b2 = y2 - a2 * x2;
  108.     ll xu1 = (b2 - b1) / (a1 - a2);
  109.     ll yu1 = a1 * xu1 + b1;
  110.     ret.push_back({ xu1, yu1 });
  111.  
  112.     ll a3 = -1;
  113.     ll a4 = 1;
  114.     ll b3 = y1 - a3 * x1;
  115.     ll b4 = y2 - a4 * x2;
  116.     ll xu2 = (b4 - b3) / (a3 - a4);
  117.     ll yu2 = a3 * xu2 + b3;
  118.     ret.push_back({ xu2, yu2 });
  119.  
  120.     /* ret.push_back({ (x1 + y2 - y1 + x2) / 2, (y2 + y1 + x2 - x1) / 2 });
  121.      ret.push_back({ (x1 - y2 + y1 + x2) / 2, (y2 + y1 - x2 + x1) / 2 });*/
  122.      //}
  123.     return ret;
  124. }
  125.  
  126. void solve() {
  127.     ll n;
  128.     cin >> n;
  129.     vector<pll> sp(n);
  130.     forp(i, 0, n) cin >> sp[i].F >> sp[i].S;
  131.     if (n == 1) {
  132.         cout << "YES\n" << sp[0].first << ' ' << sp[0].second << '\n';
  133.         return;
  134.     }
  135.     //sort(all(sp));
  136.     pii qs = start_queens(sp);
  137.     pll a = sp[qs.first];
  138.     pll b = sp[qs.second];
  139.     vector<pll> points = make_intersect(a, b);
  140.     for (pll ans : points) {
  141.         bool f = true;
  142.         forp(i, 0, n) {
  143.             if (!check_point(sp[i], ans)) {
  144.                 f = false;
  145.                 break;
  146.             }
  147.         }
  148.         if (f) {
  149.             cout << "YES\n" << ans.first << ' ' << ans.second << '\n';
  150.             return;
  151.         }
  152.     }
  153.     cout << "NO\n";
  154. }
  155.  
  156. int main() {
  157.     int t;
  158.     cin >> t;
  159.     //t = 1;
  160.     while (t > 0) {
  161.         solve();
  162.         t--;
  163.     }
  164. }
Tags: icpc Ural
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement