Cod sursa(job #1539060)

Utilizator CartofJohnsonFMI Tanasescu Andrei CartofJohnson Data 30 noiembrie 2015 10:09:00
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 3.29 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct P{double x; double y;};
struct P mirel[100005],buff[100005],S[100005],A[100005],B[100005];int n,i,j,T[100005]; 
int PCX(const void* a, const void* b){return ((struct P*)a)->x - ((struct P*)b)->x;}
int PCY(const void* a, const void* b){return ((struct P*)a)->y - ((struct P*)b)->y;}
double D2(struct P x, struct P y){return (y.x-x.x)*(y.x-x.x) + (y.y-x.y)*(y.y-x.y);};
void swap(struct P x, struct P y){double k=x.x; x.x=y.x; y.x=k; k=x.y; x.y=y.y; y.y=k;};
int MX(int l, int r){//mediana dupa X. Returneaza primul indice din a doua parte. 0->n-1
	int v=(r+l)>>1,t=0,q;
	for(;t<v;l++){
		for(q=1;l<r-1 && mirel[l].x==mirel[l+1].x;l++,q++);
		if(t+q>=v){if(t+q>v && t+q-v<v-t)t+=q;break;}
		t+=q;};return t+1;}
int MY(int l, int r){//mediana dupa Y. Returneaza primul indice din a doua parte. 0->n-1
	int v=(r+l)>>1,t=0,q;
	for(;t<v;l++){
		for(q=1;l<r-1 && mirel[l].y==mirel[l+1].y;l++,q++);
		if(t+q>=v){if(t+q>v && t+q-v<v-t)t+=q;break;}
		t+=q;};return t+1;}
void merge(int l, int m){
	int qq=0;
	for(i=l,j=m;i<l+T[l] || j<m+T[m];){
		if(i<l+T[l] && j<m+T[m]){
			if(S[i].y<S[j].y)buff[qq++]=S[i++];
			else buff[qq++]=S[j++];
		} else if(i<l+T[l])buff[qq++]=S[i++];
		else buff[qq++]=S[j++];
	}
	T[l]=qq;for(i=0;i<T[l];i++)S[l+i]=buff[i];
}
double DIV(int l, int r){//D&C. 0->n-1
	if(l>=r)return 999999;//s-NaN
	if(l+1==r){S[l]=mirel[l],T[l]=1;return 999999;}
	if(r-l==2){
		T[l]=2;S[l]=mirel[l];S[r-1]=mirel[r-1];
		if(S[l].y>S[r-1].y)swap(S[l],S[r-1]);
		A[l]=mirel[l];
		B[l]=mirel[r-1];
		return D2(S[l],S[r-1]);
	}
	int m=MX(l,r);//altfel partitionam
	if(mirel[l].x == mirel[r-1].x){//datorita algoritmului glorios de mediana asta merge si fara if DAR se repartizeaza 1-rest ceea ce ne intristeaza ;-; asa ca trebuie caz special 
		m=MY(l,r);
		double ly=(mirel[m].y+mirel[m-1].y)/2,LD=DIV(l,m),RD=DIV(m,r);if(LD>RD)LD=RD,A[l]=A[m],B[l]=B[m];//LD := minimul
		for(i=l;i<l+T[l];i++)if(ly-mirel[i].y>LD)swap(S[i],S[l+--T[l]]);//stergerea lui mircea
		for(i=m;i<m+T[m];i++)if(mirel[i].y-ly>LD)swap(S[i],S[m+--T[m]]);//stergerea lui mircea
		int lS,rS=0;for(lS=0;lS<T[l];lS++){//acum in S cautam ce ne trebuie
			for(;rS>0 && S[m+rS].x>S[l+lS].x-LD;rS--);//rollback
			for(;rS<T[m] && S[m+rS].x<=S[l+lS].x+LD;rS++){
				if(LD>D2(S[l+lS],S[m+rS]))
					LD=D2(S[l+lS],S[m+rS]),
					A[l]=S[l+lS],B[l]=S[m+rS];
			}//check
		};merge(l,m);return LD;}
	double lx=(mirel[m].x+mirel[m-1].x)/2,LD=DIV(l,m),RD=DIV(m,r);if(LD>RD)LD=RD,A[l]=A[m],B[l]=B[m];//LD := minimul
	for(i=l;i<l+T[l];i++)if(lx-mirel[i].x>LD)swap(S[i],S[l+--T[l]]);//stergerea lui mircea
	for(i=m;i<m+T[m];i++)if(mirel[i].x-lx>LD)swap(S[i],S[m+--T[m]]);//stergerea lui mircea
	int lS,rS=0;for(lS=0;lS<T[l];lS++){//acum in S cautam ce ne trebuie
		for(;rS>0 && S[m+rS].y>S[l+lS].y-LD;rS--);//rollback
		for(;rS<T[m] && S[m+rS].y<=S[l+lS].y+LD;rS++){
			if(LD>D2(S[l+lS],S[m+rS]))
				LD=D2(S[l+lS],S[m+rS]),
				A[l]=S[l+lS],B[l]=S[m+rS];
		}//check
	};merge(l,m);return LD;}
int main(){
	freopen("cmap.in",stdin,"r");
	freopen("cmap.out",stdout,"w");
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%lf %lf",&(mirel[i].x),&(mirel[i].y));
	qsort(mirel,n,sizeof(struct P),PCX);
	printf("%lf: (%lf,%lf) - (%lf,%lf)",sqrt(DIV(0,n)),A[0].x,A[0].y,B[0].x,B[0].y);
	return 0;
}