Cod sursa(job #1835637)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 27 decembrie 2016 11:49:49
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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()+a.x;
    t.y=u.imag()+a.y;
    return t;
}

inline bool egal(punct a, punct b){
    return ((myabs(a.x-b.x)<=EPS)&&(myabs(a.y-b.y)<=EPS));
}

inline int cauta(punct a){
    int rez=0;
    for(int pas=1<<LOGN; pas; pas>>=1){
        if((rez+pas<=n)&&(egal(v[rez+pas], a))) return 1;
        else if((rez+pas<=n)&&(v[rez+pas]<=a)) rez+=pas;
    }
    if((rez>0)&&(egal(v[rez], a))) return 1;
    else return 0;
}

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;
}