Cod sursa(job #1073848)

Utilizator jul123Iulia Duta jul123 Data 6 ianuarie 2014 21:05:21
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.86 kb
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define EPS 10e-4
using namespace std;

typedef struct puncte{
double x;
double y;}punct;
punct p[10000];
int n;
int cmp(punct a, punct b)
{
    if(abs(a.x-b.x)<EPS)
        return(a.y<b.y);
    else
        return(a.x<b.x);
}
int binary_Search(int st, int dr, punct a)
{
        int mij=(st+dr)/2;
        if(abs(p[mij].x-a.x)<EPS && abs(p[mij].y-a.y)<EPS)
            return mij;
        if(st<=dr)
        {
            if(cmp(p[mij], a))
                return binary_Search(mij+1, dr, a);
            else return binary_Search(st, mij-1, a);
        }
        return -1;


    }


int main()
{
    FILE *fin, *fout;
    fin=fopen("patrate3.in", "r");
    fout=fopen("patrate3.out", "w");

    int i, nr=0, j;
    punct val2, val1;
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++)
        {
            fscanf(fin, "%lf %lf", &p[i].x, &p[i].y);
        }
    sort(p, p+n, cmp);

    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            if(p[i].y<p[j].y)
            {val1.x=(p[i].x+p[j].x)/2+abs(p[j].y-p[i].y)/2;
            val1.y=(p[i].y+p[j].y)/2-abs(p[j].x-p[i].x)/2;
            val2.x=(p[i].x+p[j].x)/2-abs(p[j].y-p[i].y)/2;
            val2.y=(p[i].y+p[j].y)/2+abs(p[j].x-p[i].x)/2;
            if(binary_Search(0, n-1, val1)!=-1 && binary_Search(0, n-1, val2)!=-1)
                nr++;}
                else
                  {val1.x=(p[i].x+p[j].x)/2-abs(p[j].y-p[i].y)/2;
                val1.y=(p[i].y+p[j].y)/2-abs(p[j].x-p[i].x)/2;
                val2.x=(p[i].x+p[j].x)/2+abs(p[j].y-p[i].y)/2;
                val2.y=(p[i].y+p[j].y)/2+abs(p[j].x-p[i].x)/2;
                if(binary_Search(0, n-1, val1)!=-1 && binary_Search(0, n-1, val2)!=-1)
                    nr++;}
       }

        fprintf(fout, "%d", nr/2);
}