Cod sursa(job #16987)

Utilizator supernovaMihai Pantis supernova Data 14 februarie 2007 17:54:22
Problema Patrate 3 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <stdio.h>

struct
{
    float x,y;
} p[1001];
int n,nsq=0;
float epsilon=0.00001;

float abs (float f) { if(f > 0.0) return f; else return -f; }

void citire(void)
{
    int i;
    FILE *f=fopen("patrate3.in","r");
    
    fscanf(f,"%d",&n);
    for(i=0;i<n;i++) fscanf(f,"%f %f",&p[i].x,&p[i].y);
    
    fclose(f);
}

void sort(void)
{
    int i,j;
    float aux;
    
    for(i=0;i<n;i++)
	for(j=0;j<i;j++)
	{
	    if((p[j].x-p[i].x > epsilon) || ( (abs(p[j].x-p[i].x)<epsilon)  && p[j].y-p[i].y > epsilon) )
	    {
		aux=p[i].x;p[i].x=p[j].x;p[j].x=aux;
		aux=p[i].y;p[i].y=p[j].y;p[j].y=aux;
	    }
	}
}

void print(void)
{
    int i;
    for(i=0;i<n;i++)
    {
	printf("%f %f\n",p[i].x,p[i].y);
    }
}

int checkpoint (float x, float y)
{
        
    int min=0,max=n-1,med;
    while(max>min+1)
    {
	med=(min+max)/2;
	if((p[med].x-x > epsilon) || ( (abs(p[med].x-x)<epsilon)  && p[med].y-y > epsilon) ) max=med;
	else min=med;
    }
    
    //printf("%f %f %f %f %f %f\n",x,y,p[min].x,p[min].y,p[max].x,p[max].y);
    if((abs(p[max].x-x)<epsilon) && (abs(p[max].y-y)<epsilon)) { printf("!"); return 1;}
    if((abs(p[min].x-x)<epsilon) && (abs(p[min].y-y)<epsilon)) { printf("?"); return 1;}
    if(min>1) if((abs(p[min-1].x-x)<epsilon) && (abs(p[min-1].y-y)<epsilon)) { printf("?"); return 1;}
    if(max<n-1) if((abs(p[max+1].x-x)<epsilon) && (abs(p[max+1].y-y)<epsilon)) { printf("?"); return 1;}
    return 0;
}

void output(void)
{
    FILE *f=fopen("patrate3.out","w");
    fprintf(f,"%d\n",nsq/2);
    fclose(f);
}

int main(void)
{
    int i,j;
    float mijx,mijy,dx,dy,x2,y2,x3,y3;
    
    citire();
    sort();
    print();
    
    for(i=0;i<n;i++)
	for(j=0;j<i;j++)
	{
	    mijx=(p[i].x+p[j].x)/2; mijy=(p[i].y+p[j].y)/2;
	    dx=abs(mijx-p[i].x); dy=abs(mijy-p[i].y);
	    if(p[i].y-p[j].y>epsilon)
	    {
		x2=mijx+dy; y2=mijy-dx; x3=mijx-dy; y3=mijy+dx;
	    }
	    else
	    {
		x2=mijx-dy; y2=mijy-dx; x3=mijx+dy; y3=mijy+dx;
	    }
	
	    if(checkpoint(x2,y2)&&checkpoint(x3,y3)) 
	    {
		nsq++;
		printf("New square: %.2f %.2f, %.2f %.2f  <=>  %.2f %.2f, %.2f %.2f\n",p[i].x,p[i].y,p[j].x,p[j].y,x2,y2,x3,y3);
	    }
	}
    
    output();
    return 0;
    
}