K_Y_M_bl_C

usaco nov2k11silver2

Nov 22nd, 2016
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:256000000")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. typedef unsigned long long ull;
  9. typedef long long ll;
  10. typedef pair<int, int> pii;
  11. typedef vector<int> vi;
  12. typedef pair<string, int> psi;
  13. typedef vector<string> vs;
  14. typedef pair<ll, ll> pll;
  15. typedef vector<ll> vll;
  16. typedef vector<char> vc;
  17. typedef vector<pii> vpii;
  18. typedef vector<pair<ll, ll> > vpll;
  19. typedef long double ld;
  20.  
  21. #define forn(i, n) for (int i = 0; i < (int)n; i++)
  22. #define for1(i, n) for (int i = 1; i <= (int)n; i++)
  23. #define forq(i, s, t) for (int i = s; i <= t; i++)
  24. #define ford(i, s, t) for (int i = s; i >= t; i--)
  25. #define mk make_pair
  26. #define inb push_back
  27. #define outb pop_back
  28. #define all(v) v.begin(), v.end()
  29. #define X first
  30. #define Y second
  31. #define TIME clock() * 1.0 / CLOCKS_PER_SEC
  32. #define sqr(x) (x) * (x)
  33. #define y1 amdknkgsdaasdwapgnpikn
  34. //
  35. #define mp make_pair
  36. #define pb push_back
  37. #define XX first
  38. #define YY second
  39. //
  40.  
  41. const ld EPS = 1e-9;
  42. const ld pi = acos(-1.0);
  43.  
  44. const int MAXN = (int)1e5 + 7;
  45. const int INF = (int)2e9;
  46. const ll LINF = (ll)7e18;
  47. const ll MOD = (ll)1e9 + 7;
  48. const int CHASH = (ll)239017;
  49. const ld DINF = (ld)1000000000000000.0;
  50.  
  51. int n, d;
  52. pii a[MAXN];
  53.  
  54. int solve()
  55. {
  56.     scanf("%d %d", &n, &d);
  57.     forn(i, n)
  58.         scanf("%d %d", &a[i].X, &a[i].Y);
  59.     sort(a, a + n);
  60.     set<pii> q;
  61.     ll ans = 0;
  62.     int r = 1;
  63.     forn(i, n)
  64.     {
  65.         q.erase(mk(a[i].Y, i));
  66.         while (r < n && a[i].X + d < a[r].X)
  67.         {
  68.             q.insert(a[r]);
  69.             ++r;
  70.         }
  71.         --r;
  72.         set<pii>::iterator itl = q.upper_bound(mk(a[i].Y - d, INF));
  73.         set<pii>::iterator ritr = q.lower_bound(mk(a[i].Y + d, -1));
  74.         ++ritr;
  75.         pii lt = (*itl);
  76.         if (ritr == q.begin())
  77.             continue;
  78.         --ritr;
  79.         pii rt = (*ritr);
  80.         if (lt.Y != rt.Y && lt.X > a[i].Y - d && lt.X < a[i].Y + d && rt.X > a[i].Y - d && rt.X < a[i].Y + d)
  81.             puts("-1"), exit(0);
  82.         if (rt.X > a[i].Y - d && rt.X < a[i].Y + d)
  83.         {
  84.             if (ans)
  85.                 puts("-1"), exit(0);
  86.             pii Q = a[rt.Y];
  87.             ans = abs(Q.X - a[i].X) * abs(Q.Y - a[i].Y);
  88.         }
  89.         else
  90.         {
  91.             if (lt.X > a[i].Y - d && lt.X < a[i].Y + d)
  92.             {
  93.                 if (ans)
  94.                     puts("-1"), exit(0);
  95.                 pii Q = a[lt.Y];
  96.                 ans = abs(Q.X - a[i].X) * abs(Q.Y - a[i].Y);
  97.             }
  98.         }
  99.     }
  100.     printf("%lld", ans);
  101.     return 0;
  102. }
  103.  
  104. int main()
  105. {
  106.     freopen("input.txt", "r", stdin);
  107.     freopen("output.txt", "w", stdout);
  108.     solve();
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment