Cod sursa(job #834808)

Utilizator visanrVisan Radu visanr Data 15 decembrie 2012 13:13:53
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <tr1/unordered_map>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <ctime>
using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define leftSon (node << 1)
#define rightSon ((node << 1) + 1)
#define nmax 1010
#define eps 1e-6

int N, i, j, ans;
pair<double, double> V[nmax];

int BS(double X, double Y)
{
    int left = 0, right = N + 1, mid;
    while(left + 1 < right)
    {
        mid = (left + right) / 2;
        double difX = X - V[mid].f;
        double difY = Y - V[mid].s;
        if(-eps < difX && difX < eps && -eps < difY && difY < eps) return mid;
        if(-eps < difX && difX < eps)
        {
            if(difY > eps) left = mid;
            else right = mid;
        }else
        {
            if(difX > eps) left = mid;
            else right = mid;
        }
    }
    double difX = X - V[right].f;
    double difY = Y - V[right].s;
    if(-eps < difX && difX < eps && -eps < difY && difY < eps) return right;
    else return -1;
}

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    scanf("%i", &N);
    for(i = 1; i <= N; i++)
        scanf("%lf %lf", &V[i].f, &V[i].s);
    sort(V + 1, V + N + 1);
    for(i = 1; i <= N; i++)
        for(j = i + 1; j <= N; j++)
            if(BS(V[j].f + fabs(V[i].s - V[j].s), V[j].s + fabs(V[i].f - V[j].f)) != -1)
                if(BS(V[i].f + fabs(V[i].s - V[j].s), V[i].s + fabs(V[i].f - V[j].f)) != -1)
                    ans ++;
    printf("%i\n", ans);
    return 0;
}