Cod sursa(job #1835630)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 27 decembrie 2016 11:41:34
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <cmath>
#include <complex>
#include <algorithm>

#define cpx std::complex <double>

#define punct std::pair <double, double>
#define x first
#define y second

#define EPS 0.001

#define MAXN 1500
#define LOGN 10

const double PI=acos(-1);

punct v[MAXN+1];
int n;

inline double myabs(double x){
    if(x<0) return -x;
    else return x;
}

inline punct f(punct a, punct b, int ang){
    double aux=(double)ang*PI/180;
    cpx u=cpx(cos(aux), sin(aux)), v=cpx(b.x-a.x, b.y-a.y);
    u*=v;
    punct t;
    t.x=u.real();
    t.y=u.imag();
    return t;
}

inline int cauta(punct a){
    int rez=0;
    for(int pas=1<<LOGN; pas; pas>>=1)
        if((rez+pas<=n)&&(v[rez+pas]<=a))
            rez+=pas;
    return (((rez>0)&&(myabs(v[rez].x-a.x)<=EPS)&&(myabs(v[rez].y-a.y<=EPS)))||((rez+1<=n)&&(myabs(v[rez+1].x-a.x)<=EPS)&&(myabs(v[rez+1].y-a.y)<=EPS)));
}

int main(){
    FILE *fin, *fout;
    fin=fopen("triang.in", "r");
    fout=fopen("triang.out", "w");

    fscanf(fin, "%d", &n);

    for(int i=1; i<=n; i++)
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);

    std::sort(v+1, v+n+1);

    int ans=0;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            ans+=cauta(f(v[i], v[j], 60))+cauta(f(v[i], v[j], -60));

    ans/=3;
    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}