Cod sursa(job #1592262)

Utilizator razvandRazvan Dumitru razvand Data 7 februarie 2016 13:22:43
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
#define EPS 0.001

using namespace std;

ifstream in("triang.in");
ofstream out("triang.out");

const double sin60 = sin(60*M_PI/180);
const double cos60 = cos(60*M_PI/180);

struct p {
    double x;
    double y;
};

int n;
p v[1501];
p t;

double fabs (double a) {
    if (a<0)
        return -a;
    return a;
}

int check (p a,p b) {
    if (fabs (a.x-b.x)<EPS) {
        if (fabs (a.y-b.y)<EPS)
            return 0;
        else if (a.y>b.y)
            return -1;
        else
            return 1;

    }
    else if(a.x>b.x)
        return -1;
    else
        return 1;
}

bool cmp(p a, p b) {
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}

bool caut(p t1, int st, int dr) {
    int mid = (st+dr)/2;
    if(st > dr)
        return false;
    int ch = check(t1, v[mid]);
    if(ch < 0)
        return caut(t1, mid+1, dr);
    if(ch > 0)
        return caut(t1, st, mid-1);
    return true;
}

int main() {
    in >> n;
    for(int i = 1; i <= n; i++) {
        in >> t.x >> t.y;
        v[i] = t;
    }
    sort(v+1, v+n+1, cmp);
    long long rez = 0;
    for(int i = 1; i < n; i++) {
        for(int j = i+1; j <= n; j++) {
            t.x=(v[j].x-v[i].x)*cos60-(v[j].y-v[i].y)*sin60+v[i].x;
            t.y=(v[j].x-v[i].x)*sin60+(v[j].y-v[i].y)*cos60+v[i].y;
            rez+= caut(t, 1, n);
            t.x=(v[i].x-v[j].x)*cos60-(v[i].y-v[j].y)*sin60+v[j].x;
            t.y=(v[i].x-v[j].x)*sin60+(v[i].y-v[j].y)*cos60+v[j].y;
            rez+= caut(t, 1, n);
        }
    }
    out << rez;
    return 0;
}