Cod sursa(job #1865045)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 februarie 2017 11:27:08
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
# include <fstream>
# include <algorithm>
# define DIM 1510
# define EPS 1e-4
# define sin 0.8660254
# define cos 0.5
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
struct punct{
    double x;
    double y;
};
punct v[DIM],a;
int n,i,j,Pas,sol;
bool cmp(punct a,punct b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
bool egalitate(double a,double b){
    if(a-b<=EPS&&a-b>=-EPS)
        return 1;
    else
        return 0;
}
bool cauta(punct a){
    int j,pas;
    for(j=0,pas=Pas;pas;pas/=2)
        if(j+pas<=n)
            if(v[j+pas].x<a.x&&(!(egalitate(v[j+pas].x,a.x))))
                j+=pas;
    j++;
    if(!egalitate(v[j].x,a.x))
        return 0;
    for(pas=Pas;pas;pas/=2)
        if(j+pas<=n){
            if(egalitate(v[j+pas].x,a.x)){
                if(egalitate(v[j+pas].y,a.y))
                    j+=pas;
                else{
                    if(v[j+pas].y<a.y)
                        j+=pas;
                }
            }
        }
    return ((egalitate(a.x,v[j].x))&&(egalitate(a.y,v[j].y)));
}
int main () {
    fin>>n;
    for(Pas=1;Pas<=n;Pas*=2);
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<n;i++){
        for(j=i+1;j<=n;j++){
            a.x=v[i].x+(v[j].x-v[i].x)*cos-(v[j].y-v[i].y)*sin;
            a.y=v[i].y+(v[j].x-v[i].x)*sin+(v[j].y-v[i].y)*cos;
            if(cauta(a))
                sol++;
            a.x=v[i].x+(v[j].x-v[i].x)*cos+(v[j].y-v[i].y)*sin;
            a.y=v[i].y-(v[j].x-v[i].x)*sin+(v[j].y-v[i].y)*cos;
            if(cauta(a))
                sol++;
        }
    }
    fout<<sol/3<<"\n";
    return 0;
}