Cod sursa(job #838541)

Utilizator SteveStefan Eniceicu Steve Data 19 decembrie 2012 22:01:37
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <stack>
#include <bitset>
#include <list>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp(a,b) make_pair (a, b)
#define ll long long
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define x first
#define y second
#define abs(a) (a > 0 ? a : -a)
#define eps 1e-5

using namespace std;

int N;
pair <double, double> v[1511];

void Citire ()
{
    ifstream fin ("triang.in");
    fin >> N;
    for (int i = 0; i < N; i++)
        fin >> v[i].x >> v[i].y;
    fin.close ();
    sort (v, v + N);
}

pair <double, double> Aflare_Coord1 (pair <double, double> a, pair <double, double> b)
{
    return mp (0.5 * (a.x + b.x) + sqrt(3.0) / 2.0 * (a.y - b.y),  0.5 * (a.y + b.y) + sqrt(3.0) / 2.0 * (b.x - a.x));
}

pair <double, double> Aflare_Coord2 (pair <double, double> a, pair <double, double> b)
{
    return mp (0.5 * (a.x + b.x) + sqrt(3.0) / 2.0 * (b.y - a.y), 0.5 * (a.y + b.y) - sqrt(3.0) / 2.0 * (b.x - a.x));
}

inline int cmp (pair <double, double> a, pair <double, double> b)
{
    if (abs (a.x - b.x) < eps)
    {
        if (abs (a.y - b.y) < eps) return 1;
        return a.y < b.y;
    }
    return a.x < b.x;
}

inline int cmp2 (pair <double, double> a, pair <double, double> b)
{
    return (abs (a.x - b.x) < eps && abs (a.y - b.y) < eps);
}

int B_Search (int i, pair <double, double> val)
{
    int step = 1 << 11;
    for (; step; step >>= 1)
        if (i + step < N && cmp (v[i + step], val)) i += step;
    if (cmp2 (v[i], val)) return 1;
    return 0;
}

int Business ()
{
    int cnt = 0;
    for (int i = 0; i < N - 2; i++)
    {
        for (int j = i + 1; j < N - 1; j++)
        {
            cnt += B_Search (j + 1, Aflare_Coord1 (v[i], v[j]));
            cnt += B_Search (j + 1, Aflare_Coord2 (v[i], v[j]));
        }
    }
    return cnt;
}

void Scriere ()
{
    ofstream fout ("triang.out");
    fout << Business ();
    fout.close ();
}

int main ()
{
    Citire ();
    Scriere ();
    return 0;
}