Cod sursa(job #748313)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 13 mai 2012 01:24:30
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;

const double emax=0.0001, sqrt3=1.73208;
const int nmax=1500;

inline int real_cmp(double x, double y){
    if (x<y){
        if (y-x<=emax){
            return 0;
        }else{
            return 1;
        }
    }else{
        if (x-y<=emax){
            return 0;
        }else{
            return -1;
        }
    }
}

struct pt{
    double x, y;
};

pt operator +(pt x, pt y){
    x.x+=y.x;
    x.y+=y.y;
    
    return x;
}

inline bool pt_cmp(pt x, pt y){
    if (!real_cmp(x.x,y.x)){
        return x.y<y.y;
    }else{
        return x.x<y.x;
    }
}


pt v[nmax+1];

int main(){
    int n, sol, auxbs;

    assert(freopen("triang.in", "r", stdin));
    assert(scanf(" %d ", &n));
    for (int i=1; i<=n; ++i){
        assert(scanf(" %lf %lf ", &v[i].x, &v[i].y));
    }
    fclose(stdin);

    sort(v+1, v+n+1, pt_cmp);
    
    /*for (int i=1; i<=n; ++i){
        fprintf(stderr, "%lf %lf\n", v[i].x, v[i].y);
    }*/

    sol=0;
    for (auxbs=1; auxbs<n; auxbs*=2){
    }
    for (int i=2; i<=n-1; ++i){
        for (int j=1; j<i; ++j){
            //fprintf(stderr, "\ni=%d j=%d\n", i, j);
            double aux;
            int pos;
            pt key, x;/*
   
            x.x=(v[i].x-v[j].x)/2;
            x.y=(v[i].y-v[j].y)/2;
            
            //fprintf(stderr, "x=(%lf, %lf)\n", x.x, x.y);

            key=key+x;
            //fprintf(stderr, "key=(%lf, %lf)\n", key.x, key.y);
            x.x*=sqrt3;
            x.y*=sqrt3;
            //fprintf(stderr, "x=(%lf, %lf)\n", x.x, x.y);
            if (v[i].y>v[j].y){
                aux=x.x;
                x.x=x.y;
                x.y=-aux;
            }else{
                aux=x.x;
                x.x=-x.y;
                x.y=aux;
            }
            //fprintf(stderr, "x=(%lf, %lf)\n", x.x, x.y);
            key=key+x;
            pos=n;*/
            for (int k=auxbs; k; k/=2){
                if (pos-k>i&&pt_cmp(key, v[pos-k])){
                    pos-=k;
                }
            }

            if (v[pos].x-key.x<=emax&& 
                v[pos].y-key.y<=emax&& key.y-v[pos].y<=emax){
                ++sol;
            }
        }
    }

    assert(freopen("triang.out", "w", stdout));
    printf("%d\n", sol);
    fclose(stdout);

    return 0;
}