Cod sursa(job #748316)

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

using namespace std;

const double emax=0.001, 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;
};

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

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

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