Cod sursa(job #2072641)

Utilizator ursuadina98Ursu Adina ursuadina98 Data 22 noiembrie 2017 00:05:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.66 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x,y;
};
double distanta(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmpX(punct a,punct b)
{
    return a.x<b.x;
}
bool cmpY(punct a,punct b)
{
    return a.y<=b.y;
}

struct minima
{
    double dis;
    punct p1,p2;
};
minima mini;
minima dist_min(int st,int dr,punct P[])
{
    if((dr-st+1)<=3)
    {
       if((dr-st+1)==3)
       {
           if(distanta(P[st],P[st+1])<distanta(P[st],P[dr]))
           {
               mini.dis=distanta(P[st],P[st+1]);
               mini.p1=P[st];
               mini.p2=P[st+1];
           }
           else
           {
                mini.dis=distanta(P[st],P[dr]);
                mini.p1=P[st];
                mini.p2=P[dr];
           }
           if(distanta(P[st+1],P[dr])<mini.dis)
           {
               mini.dis=distanta(P[st+1],P[dr]);
               mini.p1=P[st+1];
               mini.p2=P[dr];
           }

       }
       else
        if((dr-st+1)==2)
        {
           mini.dis=distanta(P[st],P[dr]);
           mini.p1=P[st];
           mini.p2=P[dr];
        }
        return mini;
    }
    else
    {
        int d;
        punct poz_x,poz_y;
        minima min_st,min_dr,min_p,min_p1;
        punct Y[100001];
        min_p1.dis=1000000001;
        d=(st+dr)/2;
        min_st=dist_min(st,d,P);
        min_dr=dist_min(d+1,dr,P);
        if(min_st.dis<min_dr.dis)
            min_p=min_st;
        else
            min_p=min_dr;
        int k=0,i,j;
        double l;
        for(i=st;i<=dr;i++)
        {
            l=distanta(P[i],P[d]);
            if(l<=min_p.dis)
                {
                    Y[k]=P[i];
                    k++;
                }
        }
        //set <punct>::iterator i,j;
        sort(Y,Y+k,cmpY);
        for(i=0;i<k-1;i++)
        {
            for(j=i+1;j<k;j++)
                if(distanta(Y[i],Y[j])<=min_p.dis)
                {
                    min_p1.dis=distanta(Y[i],Y[j]);
                    min_p1.p1=Y[i];
                    min_p1.p2=Y[j];
                }
        }
        if(min_p1.dis<min_p.dis)
        {
            min_p=min_p1;

        }
        return min_p;
    }
}
int main()
{
    int i,n;
    punct p;
    minima pct;
    punct P[100001];
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>P[i].x>>P[i].y;
    }
    pct=dist_min(0,n-1,P);
    g<<pct.dis<<endl<<pct.p1.x<<" "<<pct.p1.y<<endl<<pct.p2.x<<" "<<pct.p2.y;
    return 0;
}