Cod sursa(job #2969232)

Utilizator mmocanuMocanu Mihai-Adrian mmocanu Data 22 ianuarie 2023 19:03:13
Problema Cele mai apropiate puncte din plan Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define inl long long
#define MAXN 100005
using namespace std;
FILE *fin,*fout;

struct XY{
  inl x,y;
};

XY poit[MAXN];
XY sir[MAXN];
inl dist=1e18;

inl Read(){
  char a;
  inl x,s;
  a=fgetc(fin);
  while(a!='-' && !isdigit(a)){
    a=fgetc(fin);
  }
  if(a=='-'){
    a=fgetc(fin);
    s=-1;
  }else{
    s=1;
  }
  x=0;
  while(isdigit(a)){
    x=x*10+a-'0';
    a=fgetc(fin);
  }
  return x*s;
}

bool cmp(XY a,XY b){
  if(a.x==b.x){
    return a.y<b.y;
  }
  return a.x<b.x;
}

bool ctr(XY a,XY b){
  if(a.y==b.y){
    return a.x<b.x;
  }
  return a.y<b.y;
}

inl meter(XY a,XY b){
  return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

void Divide(int st,int dr){
  int mij,i,m,j;
  inl aux;
  if(dr-st<=2){
    if(dr-st==1){
      aux=meter(poit[st],poit[dr]);dist=dist>aux?aux:dist;
    }else{
      aux=meter(poit[st]  ,  poit[dr]);dist=dist>aux?aux:dist;
      aux=meter(poit[st+1],  poit[dr]);dist=dist>aux?aux:dist;
      aux=meter(poit[st]  ,poit[st+1]);dist=dist>aux?aux:dist;
    }
    return;
  }
  mij=(st+dr)/2;
  Divide(st,mij);
  Divide(mij,dr);
  m=0;
  for(i=st;i<=dr;i++){
    if((poit[mij].x-poit[i].x)*(poit[mij].x-poit[i].x)<=dist){
      sir[m]=poit[i];
      m++;
    }
  }
  sort(sir,sir+m,ctr);
  for(i=0;i<m;i++){
    j=i+1;
    aux=0;
    while(j<m && aux<=dist){
      aux=meter(poit[i],poit[j]);dist=dist>aux?aux:dist;
      j++;
    }
  }
}
int main(){
  int n,i;
  fin=fopen("cmap.in","r");
  fout=fopen("cmap.out","w");
  n=Read();

  for(i=0;i<n;i++){
    poit[i]={Read(),Read()};
  }

  sort(poit,poit+n,cmp);

  Divide(0,n-1);

  fprintf(fout,"%.6f",(double)sqrt(dist));

  fclose(fin);
  fclose(fout);
  return 0;
}