Cod sursa(job #1552467)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 decembrie 2015 00:39:08
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>

#define DIM 1024
#define eps 0.00001
#define x first
#define y second
using namespace std;

double Y1, y2, y3, y4, mx, my;
double x1, x2, x3, x4, dx, dy;
int N, nr; double X, Y;
pair <double, double> P[DIM];

inline double abs (double X) {
    return X > 0 ? X : -X;
}

inline int findValue (double X, double Y) {
    int st = 1, dr = N, mid;

    while (st <= dr) {
        mid = st + (dr - st) / 2;

        if (abs (P[mid].x - X) <= eps && abs (P[mid].y - Y) <= eps)
            return 1;

        if (abs (P[mid].x - X) >= eps && P[mid].x < X)                                  st = mid + 1;
        else if (abs (P[mid].x - X) <= eps && abs (P[mid].y - Y) > eps && P[mid].y < Y) st = mid + 1;
        else                                                                            dr = mid - 1;
    }

    return 0;
}

int main () {

    freopen ("patrate3.in" ,"r", stdin );
    freopen ("patrate3.out","w", stdout);

    scanf ("%d", &N);
    for (int i = 1; i <= N; i ++)
        scanf ("%lf %lf", &P[i].x, &P[i].y);

    sort (P + 1, P + N + 1);

    for (int i =   1  ; i <= N; i ++) {
    for (int j = i + 1; j <= N; j ++) {
        x1 = P[i].x; Y1 = P[i].y;
        x2 = P[j].x; y2 = P[j].y;
        mx = (x1 + x2) / 2; my = (Y1 + y2) / 2;
        dx = abs (mx - x1); dy = abs (my - Y1);

        if (Y1 < y2) {
            x3 = mx + dy; y3 = my - dx;
            x4 = mx - dy; y4 = my + dx;
        } else {
            x3 = mx - dy; y3 = my - dx;
            x4 = mx + dy; y4 = my + dx;
        }

        if (findValue (x3, y3) && findValue (x4, y4))
            nr ++;
    }}

    printf ("%d\n", nr/2);

    return 0;
}