Cod sursa(job #1864200)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 31 ianuarie 2017 16:46:47
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define eps 0.001
#define cos 0.5
#define sin 0.8660254
using namespace std;
int n, i, j, sol;
pair<double, double> v[1505];
pair<double, double> pct;
ifstream fin("triang.in");
ofstream fout("triang.out");
double modul(double x){
    if(x > 0){
        return x;
    }
    return -x;
}
int cautbin(pair<double, double> p){
    int st = 1, dr = n, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(modul(v[mid].x - p.x) < eps && modul(v[mid].y - p.y) < eps){
            return 1;
        }
        if( ( modul(v[mid].x - p.x) < eps && v[mid].y < p.y ) || v[mid].x < p.x){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    return 0;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1);
    for(i = 1; i < n; i++){
        for(j = i + 1; j <= n; j++){
            pct.x = v[i].x + (v[j].x - v[i].x) * cos - (v[j].y - v[i].y) * sin;
            pct.y = v[i].y + (v[j].x - v[i].x) * sin + (v[j].y - v[i].y) * cos;
            if(cautbin(pct) == 1){
                sol++;
            }
            pct.x = v[i].x + (v[j].x - v[i].x) * cos + (v[j].y - v[i].y) * sin;
            pct.y = v[i].y - (v[j].x - v[i].x) * sin + (v[j].y - v[i].y) * cos;
            if(cautbin(pct) == 1){
                sol++;
            }
        }
    }
    fout<< sol / 3 <<"\n";
    return 0;
}