Cod sursa(job #1052083)

Utilizator jul123Iulia Duta jul123 Data 10 decembrie 2013 20:48:51
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 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 binary_Search(double a, double b)
{
    long long i, pas=n;
    for(i = 0; pas; pas >>= 1)
        {if( p[i+pas].x < a && i+pas<n)
            i += pas;
        if(p[i+pas].x==a && i+pas<n)
            if(p[i+pas].y<b)
                i+=pas;}
    if( p[i+1].x-a<EPS && p[i+1].y-b<EPS)
        return i+1 ;
    return -1;
}
int cmp(punct a, punct b)
{
    if(a.x==b.x)
        return(a.y<b.y);
    else
        return(a.x<b.x);
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("patrate3.in", "r");
    fout=fopen("patrate3.out", "w");

    int i, nr=0, j;
    double val1x, val2x, val1y, val2y;
    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++)
        {

            val1x=(p[i].x+p[j].x)/2+abs(p[j].y-p[i].y)/2;
            val1y=(p[i].y+p[j].y)/2-abs(p[j].x-p[i].x)/2;
            val2x=(p[i].x+p[j].x)/2-abs(p[j].y-p[i].y)/2;
            val2y=(p[i].y+p[j].y)/2+abs(p[j].x-p[i].x)/2;
            if(binary_Search(val1x, val1y)!=-1 && binary_Search(val2x, val2y)!=-1)
                nr++;
       }

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