Cod sursa(job #861059)

Utilizator stoicatheoFlirk Navok stoicatheo Data 20 ianuarie 2013 22:20:34
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <algorithm>
#include <cstdio> 
using namespace std;
 
#define MAXN 1011
#define ER 1e-5
#define ABS(a) ((a) < 0 ? -(a) : (a))
 
int equal(double x, double y)
{
    double d = x - y;
 
    if (d < -ER)
        return -1;
    if (d > ER)
        return 1;
    return 0;
}
 
struct punct
{
    double x, y;
 
    bool operator<(const struct punct a) const
    {
        if (equal(x, a.x))
            return equal(x, a.x) < 0 ? 1 : 0;
        return equal(y, a.y) < 0 ? 1 : 0;
    }
};
 
int N;
punct P[MAXN];
 
void read()
{
    int i;
 
    scanf("%d", &N);
 
    for (i = 0; i < N; i++)
        scanf("%lf %lf", &P[i].x, &P[i].y);
}
 
int find(double x, double y)
{
    int i, pas;
 
    for (pas = 1; pas <= N; pas <<= 1);
 
    for (i = -1; pas; pas >>= 1)
        if (i + pas < N && (equal(P[i + pas].x, x) == -1 || (!equal(P[i + pas].x, x) && equal(P[i + pas].y, y) <= 0)))
            i += pas;
    if (i == -1)
        return 0;
 
    if (equal(x, P[i].x) || equal(y, P[i].y))
        return 0;
 
    return 1;
}
 
int main()
{
    int i, j, rez = 0;
    double mijx, mijy, dx, dy, x0, y0, x1, y1;
 
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
 
    read();
    sort(P, P + N);
 
    for (i = 0; i < N; i++)
        if (!find(P[i].x, P[i].y))
            i++, i--;
 
    for (i = 0; i < N; i++)
        for (j = i + 1; j < N; j++)
        {
            mijx = (P[i].x + P[j].x) / 2;
            mijy = (P[i].y + P[j].y) / 2;
            dx = ABS(mijx - P[i].x);
            dy = ABS(mijy - P[i].y);
            if (P[i].y < P[j].y)
            {
                x0 = mijx + dy, y0 = mijy - dx;
                x1 = mijx - dy, y1 = mijy + dx;
            }
            else
            {
                x0 = mijx - dy, y0 = mijy - dx;
                x1 = mijx + dy, y1 = mijy + dx;
            }
 
            if (find(x0, y0) && find(x1, y1))
                rez++;
        }
 
    printf("%d\n", rez / 2);
 
    return 0;
}