Cod sursa(job #1410138)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 30 martie 2015 21:19:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define DIM 1501
#define eps 1.0/1e4
#define rad3p2 0.8660254037
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
int n;
struct punct {
    double x;
    double y;
}a[DIM], pct;
bool cmp ( punct a, punct b ){

    if ( abs ( a.x - b.x ) <= eps )
        return a.y < b.y;

    return a.x < b.x;
}
bool match( punct a, punct b)
{
    return (fabs(a.x - b.x) <= eps && fabs(a.y - b.y) <= eps)? 1: 0;
}
bool bsrch(punct k, int x)
{
    int st = x + 1, dr = n, mid;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(match(k, a[mid]))
            return 1;
        if(cmp(a[mid], k))
            st = mid + 1;
        else dr = mid - 1;
    }
    return 0;
}
int main()
{
    int i, j, triang = 0;
    f >> n;
    for(int i = 1; i<=n; i++) f >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i<n; i++)
        for(int j = i + 1; j<=n; j++)
    {
        pct.x = (a[i].x - a[j].x) / 2 + rad3p2 * (a[i].y - a[j].y);
        pct.y = (a[i].y - a[j].y) / 2 + rad3p2 * (a[j].x - a[i].x);
        if(bsrch(pct, j)) triang ++;
        pct.x = (a[i].x + a[j].x) / 2 + rad3p2 * (a[j].y - a[i].y);
        pct.y = (a[i].y + a[j].y) / 2 + rad3p2 * (a[i].x - a[j].x);
        if(bsrch(pct, j)) triang ++;
    }
    g << triang;
    return 0;
}