fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <stdio.h>
  4. #include <set>
  5. #include <vector>
  6. #include <map>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <memory.h>
  10. #include <string>
  11. #include <sstream>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long LL;
  19. typedef pair<int,int> PII;
  20.  
  21. #define MP make_pair
  22. #define PB push_back
  23. #define FF first
  24. #define SS second
  25.  
  26. #define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
  27. #define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
  28. #define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
  29.  
  30. #define INF 2000000000
  31.  
  32. void remove_duplicates(vector<int>& vec) {
  33.     sort( vec.begin(), vec.end() );
  34.     vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
  35. }
  36.  
  37. int t, n, x, y;
  38.  
  39. vector<PII> pts; 
  40. vector<int> ux, uy;
  41.  
  42. map<int, int> ycnt;
  43.  
  44. int main() {
  45.     scanf("%d", &t);
  46.  
  47.     while (t--) {
  48.         vector<PII>().swap(pts);
  49.         vector<int>().swap(ux);
  50.         vector<int>().swap(uy);
  51.  
  52.         scanf("%d", &n);
  53.  
  54.         FORN(i, n) {
  55.             scanf("%d", &x);
  56.             scanf("%d", &y);
  57.             pts.PB(MP(x, y));
  58.             ux.PB(x);
  59.             uy.PB(y);
  60.         }
  61.  
  62.         if (n == 1) {
  63.             printf("0\n");
  64.             continue;
  65.         }
  66.  
  67.         sort(pts.begin(), pts.end());
  68.         remove_duplicates(ux);
  69.         remove_duplicates(uy);
  70.  
  71.         int res = INF;
  72.  
  73.         for (int i = 0; i < uy.size(); i++) {
  74.             int ym = uy[i];
  75.             for (int j = i; j < uy.size(); j++) {
  76.                 int yM = uy[j];
  77.  
  78.                 // set up left and right pointers
  79.                 int pl = 0;
  80.                 while (pts[pl].SS < ym || pts[pl].SS > yM) pl++;
  81.  
  82.                 int rect = 1; int pr = pl;
  83.                 while (rect < n / 2 + 1 && pr + 1 < n) {
  84.                     pr++;
  85.                     if (pts[pr].SS >= ym && pts[pr].SS <= yM) rect++;
  86.                 }
  87.  
  88.                 if (rect < n / 2 + 1) continue;
  89.                 res = min(res, (yM - ym) * (pts[pr].FF - pts[pl].FF));
  90.  
  91.                 while (1) {
  92.                     pl++; while (pl < n && (pts[pl].SS < ym || pts[pl].SS > yM)) pl++;
  93.                     pr++; while (pr < n && (pts[pr].SS < ym || pts[pr].SS > yM)) pr++;
  94.  
  95.                     if (pr < n) {
  96.                         res = min(res, (yM - ym) * (pts[pr].FF - pts[pl].FF));
  97.                     }
  98.                     else {
  99.                         break;
  100.                     }
  101.                 }
  102.             }
  103.         }
  104.  
  105.         printf("%d\n", res);
  106.     }
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XElevb
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!