Cod sursa(job #3037902)

Utilizator Luca529Taschina Luca Luca529 Data 26 martie 2023 17:11:47
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;

class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};

InParser fin("cmap.in");
ofstream fout("cmap.out");
struct Pct{
double i, j;
}x[100001];

bool C(Pct a, Pct b)
{if(a.i<b.i || (a.i==b.i && a.j<b.j))return 1;
 return 0;
}

double Dist(double x1, double y1, double x2, double y2)
{double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 return a;
}

double DQ(int st, int dr)
{if(dr-st+1<=3)
 {double mini=1e9;
  for(int i=st;i<dr;i++)
  for(int j=i+1;j<=dr;j++)
  mini=min(mini, Dist(x[i].i, x[i].j, x[j].i, x[j].j));

  return mini;
 }
 else
 {int mij=(st+dr)/2;
  double mini=min(DQ(st, mij), DQ(mij+1, dr));
  vector<Pct> y;

  for(int i=st;i<=dr;i++)
  if(abs(x[i].i-x[mij].i)<=mini)y.push_back(x[i]);

  for(int i=0;i<y.size()-1;i++)
  for(int j=i+1;j<y.size();j++)
  mini=min(mini, Dist(y[i].i, y[i].j, y[j].i, y[j].j));

  return mini;
 }
}

int main()
{   int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    fin>>x[i].i>>x[i].j;

    sort(x+1, x+1+n, C);
    DQ(1, n);

    fout<<fixed<<setprecision(6)<<DQ(1, n);
    return 0;
}