Cod sursa(job #1181909)

Utilizator apopeid15Apopei Daniel apopeid15 Data 4 mai 2014 11:05:54
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NMAX 1507
#define EPS 0.001
#define x first
#define y second
#define R3 1.73205080
using namespace std;
 
pair< double, double > a[NMAX];
 
inline bool cb(pair< double, double > Val, int st, int dr){
    while(st <= dr){
        int med = (st + dr) >> 1;
        if(abs(a[med].x - Val.x) < EPS && abs(a[med].y - Val.y) < EPS)
            return 1;
        if(abs(a[med].x - Val.x) < EPS)
            if(a[med].y < Val.y)
                st = med + 1;
            else
                dr = med - 1;
        else
            if(a[med].x < Val.x)
                st = med + 1;
            else
                dr = med - 1;
    }
    return 0;
}
 
int main(){
    int n = 0, Ans = 0;
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){
            pair<double, double> Sol;
            Sol.x = ( a[i].x + a[i].y * R3 + a[j].x - a[j].y * R3) / 2.0;
            Sol.y = (-a[i].x * R3 + a[i].y + a[j].y + a[j].x * R3) / 2.0;
            Ans += cb(Sol, 1, n);
            Sol.x = (a[i].x - a[i].y * R3 + a[j].x + a[j].y * R3) / 2.0;
            Sol.y = (a[i].x * R3 + a[i].y + a[j].y - a[j].x * R3) / 2.0;
            Ans += cb(Sol, 1, n);
        }
    printf("%d", Ans / 3);
    return 0;
}