Cod sursa(job #2089049)

Utilizator valentinoltyanOltyan Valentin valentinoltyan Data 16 decembrie 2017 10:34:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define x first
#define y second
using namespace std;

pair<int,int>pct[100005];
pair<int,int>pct2[100005];
int n,k,d;
double s;
double minim(int s,int n)
{
    double m=99999999;
    for(int i=s;i<n-1;i++)
        for(int j=i+1;j<n;j++)
        {
            double k=0;
            k=sqrt(1.0*(pct[j].x-pct[i].x)*(pct[j].x-pct[i].x)+(pct[j].y-pct[i].y)*(pct[j].y-pct[i].y));
            m=min(m,k);
        }
    return m;
}
void sol()
{
    k=0;
    for(int i=n/2;i>=0&&k<=4;i--)
    {
        if(pct[i].x>=d-s)
            pct2[k]={pct[i].x,pct[i].y},k++;
        else break;
    }
    int l=k+4;
    for(int i=n/2+1;i<n&&k<=l;i++)
    {
        if(pct[i].x<=d+s)
            pct2[k]={pct[i].x,pct[i].y},k++;
        else break;
    }
}
int main()
{
    ifstream f ("cmap.in");
    ofstream g ("cmap.out");
    f>>n;
    for(int i=0;i<n;i++)
    {
        int a,b;
        f>>a>>b;
        pct[i]={a,b};
    }
    sort(pct,pct+n);
    double ss=minim(0,n/2);
    double sd=minim(n/2,n-1);
    d=(pct[n/2].x+pct[n/2+1].x)/2;
    s=min(ss,sd);
    sol;
    sort(pct2,pct2+k);
    for(int i=0;i<k-1;i++)
        for(int j=i+1;j<k;j++)
        {
            double c;
            c=sqrt((pct2[j].x-pct2[i].x)*(pct2[j].x-pct2[i].x)+(pct2[j].y-pct2[i].y)*(pct2[j].y-pct2[i].y));
            s=min(s,c);
        }
    g<<setprecision(6)<<fixed<<s;
    return 0;
}