Cod sursa(job #1081871)

Utilizator maritimCristian Lambru maritim Data 13 ianuarie 2014 22:23:53
Problema Patrate 3 Scor 85
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.89 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
 
#define er 0.0000001
 
typedef struct
{
    double m;
    double d;
    double x;
    double y;
} dreapta;
 
dreapta A[500100];
dreapta P[1001];
int N;
int nr;
int MAX;
double ct = 0;
 
int compara (double a,double b)
{
    if (fabs (a-b)<=0.00001)
        return 1;
    return 0;
}
 
void citire(void)
{
    FILE *f = fopen("patrate3.in","r");
     
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(f,"%lf %lf",&P[i].m,&P[i].d);
     
    fclose(f);
}
 
void prelucrare(void)
{
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
        {
            int semn;
            A[++nr].m = (P[i].d-P[j].d)/(P[i].m-P[j].m);
            A[nr].d = sqrt((P[i].d-P[j].d)*(P[i].d-P[j].d) + (P[i].m-P[j].m)*(P[i].m-P[j].m));
            A[nr].x = (P[i].m+P[j].m)/2;
            A[nr].y = (P[i].d+P[j].d)/2;
        }
}
 
int poz(int li,int ls)
{
    dreapta a = A[(li+ls)/2];
    A[(li+ls)/2] = A[li];
    A[li] = a;
    int i1 = 0;
    int j1 = -1;
    int c = 0;
    while(li<ls)
    {
        if((double)A[li].d>(double)A[ls].d)
        {
            a = A[li];
            A[li] = A[ls];
            A[ls] = a;
            c = -i1;
            i1 = -j1;
            j1 = c;
        }
        li += i1;
        ls += j1;
    }
    return li;
}
 
void quicksort(int li,int ls)
{
    if(li<ls)
    {
        int k = poz(li,ls);
        quicksort(li,k-1);
        quicksort(k+1,ls);
    }
}
 
void solve(void)
{
    int i=1;
    while(i<=nr)
    {
        int j=i+1;
        while(compara(A[j].d,A[i].d))
        {
            if(compara(A[i].m*A[j].m,-1) && compara(A[i].x,A[j].x) && compara(A[i].y,A[j].y))
                MAX ++;
            j ++;
        }
        i ++;
    }
}
 
int main()
{
    FILE *g = fopen("patrate3.out","w");
     
    citire();
    prelucrare();
    quicksort(1,nr);
    solve();
    fprintf(g,"%d",MAX);
     
    fclose(g);
    return 0;
}