Mai intai trebuie sa te autentifici.
Cod sursa(job #1831574)
Utilizator | Data | 18 decembrie 2016 12:20:46 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.44 kb |
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct point{
int x, y;
};
int n;
vector<point> points;
vector<point> points2;
void in(){
ifstream fin("cmap.in");
fin >> n;
for (int i = 0; i < n; i++)
{
point p;
fin >> p.x >> p.y;
points.push_back(p);
}
}
bool lessX(point a, point b){
return a.x < b.x;
}
bool lessY(point a, point b){
return a.y < b.y;
}
double dist(point a, point b){
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double minDist(int s, int e){
if (e - s == 1){
//2 points
return dist(points[s], points[e]);
}
else if (e - s == 2){
//3 points
double d12 = dist(points[s], points[s + 1]);
double d23 = dist(points[s + 1], points[e]);
double d13 = dist(points[s], points[e]);
return min(d12, min(d23, d13));
}
else{
int mid = (e + s) / 2;
double d = min(minDist(s, mid), minDist(mid + 1, e));
vector<point> close;
int i = mid;
while (i >= s && points[mid + 1].x - points[i].x < d){
close.push_back(points[i]);
i--;
}
i = mid + 1;
while (i <= e && points[i].x - points[mid].x <= d){
close.push_back(points[i]);
i++;
}
sort(close.begin(), close.end(), lessY);
if (close.size() > 0){
//need to check for interferences
for (int i = 0; i < close.size(); i++)
{
for (int j = i+1; j < min(i + 8, (int)close.size()); j++)
{
if (abs(close[i].y - close[j].y) <= d){
d = min(d, dist(close[i], close[j]));
}
}
}
}
/*int i = mid;
while (i >= s && points[mid + 1].x - points[i].x < d){
left.push_back(points[i]);
i--;
}
sort(left.begin(), left.end(), lessY);
i = mid + 1;
while (i <= e && points[i].x - points[mid].x <= d){
right.push_back(points[i]);
i++;
}
sort(right.begin(), right.end(), lessY);
if (right.size() > 0 && left.size() > 0){
//need to check for interferences
for (int i = 0; i < left.size(); i++)
{
for (int j = 0; j < right.size(); j++)
{
if (abs(left[i].y - right[j].y) <= d){
d = min(d, dist(left[i],right[j]));
}
}
}
}*/
return d;
}
}
int main(){
in();
points2 = points;
sort(points.begin(), points.end(), lessX);
int a = 0, b = n-1;
double d = minDist(a, b);
ofstream f("cmap.out");
f << fixed << setprecision(6) << d;
return 0;
}