Cod sursa(job #916703)

Utilizator cruceruvladCruceru Vlad cruceruvlad Data 16 martie 2013 19:53:46
Problema Patrate 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define EPS 0.0001
#define NMax 1005
typedef struct { double x, y; } coord;
 
using namespace std;
 
int N, cnt = 0;
coord v[NMax];
 
int cmp(coord A, coord B)
{
    if (A.x != B.x) return (A.x < B.x);
    return A.y < B.y;
}
 
int BS(double xx, double yy)
{
    int l, r, m;
     
    l = 0; r = N-1;
    while (l <= r)
    {
          m = ((l + r) >> 1);
          if (fabs(v[m].x - xx) < EPS && fabs(v[m].y - yy) < EPS)
             return m;
          else if (v[m].x < xx || (fabs(v[m].x - xx) < EPS && v[m].y < yy))
             l = m+1;
          else if (v[m].x > xx || (fabs(v[m].x - xx) < EPS && v[m].y > yy))
             r = m-1;
    }
     
    return -1;
}
 
int main(void)
{
    int i, j, ok;
    coord A, B; double mx, my, x0, y0, x1, y1, dx, dy;
     
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
     
    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    sort(v+0, v+N, cmp);
     
 
    for (i = 0; i < N; i++)
        for (j = i+1; j < N; j++)
            if (i != j)
            {
 
   
               mx = (v[i].x + v[j].x) / 2, my = (v[i].y + v[j].y) / 2;
               dx = fabs(mx - v[i].x), dy = fabs(my - v[i].y);
               if (v[i].y < v[j].y)
               {
                  x0 = mx + dy, y0 = my - dx;
                  x1 = mx - dy, y1 = my + dx;
               }
               else
               {
                  x0 = mx - dy, y0 = my - dx;
                  x1 = mx + dy, y1 = my + dx;
               }
               /* --- */
                
               ok = BS(x0, y0);
               if (ok == -1) continue;
               ok = BS(x1, y1);
               if (ok == -1) continue;
                
               cnt++;
            }    
     
    printf("%d\n", cnt/2);
     
    return 0;
}