Cod sursa(job #1223836)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 28 august 2014 22:57:20
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.41 kb
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define INFL "patrate3.in"
#define OUTFL "patrate3.out"

#define nmax 1010
#define eps 1e-6

struct point {
    double x, y;

    point() {}
    point(double _x, double _y) : x(_x), y(_y) {}

    bool operator < (const point &p) const {
        if(fabs(x - p.x) > eps)
            return p.x - x > 0;
        return p.y - y > 0;
    }

    bool operator == (const point &p) const {
        return fabs(x - p.x) <= eps && fabs(y - p.y) <= eps;
    }
};

int n;
vector< point > v;

void read() {
    scanf("%d", &n);

    double x, y;
    for(int i=1; i<=n; ++i) {
        scanf("%lf%lf", &x, &y);
        v.push_back(point(x, y));

        //cout << v[i-1].first << " " << v[i-1].second << endl;
    }
}

int cauta(point p) {
    int st = 0, dr = n-1, mij = 0;

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

        if(v[mij] == p)
            return mij;
        else if(v[mij] < p)
            st = mij + 1;
        else
            dr = mij - 1;
    }

    return -1;
}

void solve() {
    sort(v.begin(), v.end());

    int ans = 0;
    for(int i=0; i<n; ++i)
        for(int j=i+1; j<n; ++j) {
            double mx = (v[i].x + v[j].x)/2.0;
            double my = (v[i].y + v[j].y)/2.0;

            double dx = fabs(mx - v[i].x);
            double dy = fabs(my - v[i].y);

            point p1, p2;

            if(v[j].y - v[i].y > 0) {
                p1.x = mx + dy;
                p1.y = my - dx;

                p2.x = mx - dy;
                p2.y = my + dx;
            }
            else {
                p1.x = mx - dy;
                p1.y = my - dx;

                p2.x = mx + dy;
                p2.y = my + dx;
            }

            int i1 = cauta(p1);
            if(i1 == -1)
                continue;

            int i2 = cauta(p2);
            if(i2 == -1)
                continue;

            ++ans;
        }

    printf("%d", ans/2);
}

int main() {
//#define ONLINE_JUDGE 1
#ifndef ONLINE_JUDGE
	freopen(INFL, "r", stdin);
	freopen(OUTFL, "w", stdout);
#endif

	read();
	solve();

	return 0;
}