Cod sursa(job #1082314)

Utilizator impulseBagu Alexandru impulse Data 14 ianuarie 2014 14:15:03
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
//
//  main.c
//  triang
//
//  Created by Alexandru Bâgu on 1/13/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

const double PI = 3.141592653;
const double EPS = 1e-3;
double abs(double d) { if(d < 0) return -d; return d; }
const double eps = 1e-3;
double _sin, _cos;

typedef struct {
    double x, y;
} point;

point getPoint(point a, point b) {
    point c;
    c.x = a.x + _cos * (b.x - a.x) - _sin * (b.y - a.y);
    c.y = a.y + _sin * (b.x - a.x) + _cos * (b.y - a.y);
    return c;
}

int cmp(const double a,const double b) {
    if(a + eps < b) return -1;
    if(b + eps < a) return 1;
    return 0;
}
int comp(point a, point b) {
    if(cmp(a.x,b.x) == 0)
        return cmp(a.y,b.y);
    return cmp(a.x,b.x);
}

int bin_sea(point* P, int n, point p)
{
    int k = 1 << 30, i = 0;
    while (k >>= 1 > 0)
        if(i + k < n)
            if(comp(P[i + k], p) < 1)
                i += k;
    return comp(p, P[i]) == 0;
}
int main(int argc, const char * argv[])
{
    _cos = cos(PI / 3.0);
    _sin = sin(PI / 3.0);
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    int n;
    scanf("%d", &n);
    point* P = new point[n];
    int i, j, k;
    for(i = 0; i < n; i++)
        scanf("%le %le", &P[i].x, &P[i].y);
    
    sort(P, P + n, comp);
    
    int tr = 0;
    for(i = 0; i < n; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            tr += bin_sea(P, n, getPoint(P[i], P[j]));
            tr += bin_sea(P, n, getPoint(P[j], P[i]));
        }
    }
    
    printf("%d", tr / 3);
    return 0;
}