Cod sursa(job #6827)

Utilizator filipbFilip Cristian Buruiana filipb Data 20 ianuarie 2007 23:52:20
Problema Patrate 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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)
            {

			   /* din sursa lui Daniel ca sa determin celelalte 2 pct. */
			   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;
}