fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const double INF = 1e9;
  7.  
  8. struct Point {
  9.     int x, y;
  10.     Point() {}
  11.     Point(int x, int y): x(x), y(y) {}
  12. };
  13.  
  14. int tc, n;
  15. vector<Point> px, py;
  16. double ans;
  17.  
  18. ll sqr(int x) {
  19.     return 1ll * x * x;
  20. }
  21.  
  22. double dist(const Point &a, const Point &b) {
  23.     return sqrt(double(sqr(a.x - b.x) + sqr(a.y -b.y)));
  24. }
  25.  
  26. double perimeter(const Point &a, const Point &b, const Point &c) {
  27.     return dist(a, b) + dist(b, c) + dist(c, a);
  28. }
  29.  
  30. bool cmpX(const Point &a, const Point &b) {
  31.     if (a.x != b.x) return a.x < b.x;
  32.     return a.y < b.y;
  33. }
  34. bool cmpY(const Point &a, const Point &b) {
  35.     if (a.y != b.y) return a.y < b.y;
  36.     return a.x < b.x;
  37. }
  38.  
  39. double calc(int l, int r, const vector<Point> & PointX, const vector<Point> &PointY) {
  40.     if(r - l + 1 < 3) return INF;
  41.     int mid = (l + r) / 2;
  42.     Point pMid = PointX[mid];
  43.     vector<Point> pointByYLeft, pointByYRight;
  44.     for(int i = 0; i < PointY.size(); ++ i) {
  45.         if(cmpX(pMid, PointY[i])) {
  46.             pointByYRight.push_back(PointY[i]);
  47.         }
  48.         else {
  49.             pointByYLeft.push_back((PointY[i]));
  50.         }
  51.     }
  52.     double p = min(calc(l, mid, PointX, pointByYLeft), calc(mid + 1, r, PointX, pointByYRight));
  53.     vector<Point> temp;
  54.     for(int i = 0; i < PointY.size(); ++ i) {
  55.         if(abs(PointY[i].x - pMid.x) <= p/2) {
  56.             temp.push_back(PointY[i]);
  57.         }
  58.     }
  59.     for(int i = 0; i < temp.size(); i ++) {
  60.         for(int j = i + 1; j < temp.size(); ++ j) {
  61.             if(dist(temp[i], temp[j]) > p/2) {
  62.                 break;
  63.             }
  64.             for(int k = j + 1; k < temp.size(); ++ k) {
  65.                 if(dist(temp[i], temp[k]) > p/2) {
  66.                     break;
  67.                 }
  68.                 p = min(p, perimeter(temp[i], temp[j], temp[k]));
  69.             }
  70.         }
  71.     }
  72.     return p;
  73. }
  74.  
  75. int main() {
  76.     cin >> tc;
  77.     for (int TC = 1; TC <= tc; TC ++) {
  78.         cin >> n;
  79.         px = vector<Point> (n);
  80.         py = vector<Point> (n);
  81.         for(int i = 0; i < n; i ++) {
  82.             int x, y;
  83.             cin >> x >> y;
  84.             px[i] = py[i] = Point(x, y);
  85.         }
  86.         sort(px.begin(), px.end(), cmpX);
  87.         sort(py.begin(), py.end(), cmpY);
  88.         ans = calc(0, n - 1, px, py);
  89.         cout << "Case #" << TC << ": " << ans << '\n';
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7cKSFV
language:
C++14 (gcc 8.3)
created:
13 days 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!