Cod sursa(job #1223814)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 28 august 2014 22:15:51
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 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"

int n;
vector< pair<int, int> > v;

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

    int x, y;
    int a, b;
    for(int i=1; i<=n; ++i) {
        scanf("%d.%d", &x, &y);
        a = x*10000 + y;

        scanf("%d.%d", &x, &y);
        b = x*10000 + y;

        v.push_back(make_pair(a, b));

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

int cautaStX(int x) {
    int l = 0, r = n-1, mij;
    int sol = - 1;

    while(l <= r) {
        mij = (l+r)/2;

        if(v[mij].first == x) {
            sol = mij;
            r = mij-1;
        }
        else if(v[mij].first < x)
            l = mij + 1;
        else
            r = mij - 1;
    }

    return sol;
}

int cautaDrX(int x) {
    int l = 0, r = n-1, mij;
    int sol = - 1;

    while(l <= r) {
        mij = (l+r)/2;

        if(v[mij].first == x) {
            sol = mij;
            l = mij+1;
        }
        else if(v[mij].first < x)
            l = mij + 1;
        else
            r = mij - 1;
    }

    return sol;
}

bool cauta(int x, int y) {
    int st = cautaStX(x);
    if(st == -1)
        return false;

    int dr = cautaDrX(x);
    if(dr == -1)
        return false;

    for(int i=st; i<=dr; ++i)
        if(v[i].second == y)
            return true;

    return false;
}

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) {
            int x2, y2, x3, y3;

            int mx = (v[i].first + v[j].first)/2;
            int my = (v[i].second + v[j].second)/2;

            int dx = abs(mx - v[i].first);
            int dy = abs(my - v[i].second);

            if(v[i].second < v[j].second) {
                x2 = mx + dy;
                y2 = my - dx;

                x3 = mx - dy;
                y3 = my + dx;
            }
            else {
                x2 = mx - dy;
                y2 = my - dx;

                x3 = mx + dy;
                y3 = my + dx;
            }

            if(cauta(x2, y2) && cauta(x3, y3))
                ++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;
}