Cod sursa(job #1751848)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 2 septembrie 2016 04:37:11
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
typedef double f64;

const int NMAX = 1505;
const f64   PI = 3.141592653589, ///De schimbat parola la telefon....
           EPS = 1e-5,
           SIN = sin(PI / 3),
           COS = cos(PI / 3);


inline bool eq(f64 a, f64 b) {
    return abs(a - b) < EPS;
}

struct PDD {
    f64 x, y;

    inline PDD() { }
    inline PDD(f64 _x, f64 _y) {
        x = _x;
        y = _y;
    }

    bool operator < (const PDD &arg) const {
        return eq(x, arg.x) ? (y < arg.y) : (x < arg.x);
    }
};

vector<PDD> pts;

bool gibt(PDD arg) {
    int ant = 0;

    for(int i=1<<30; i; i>>=1) { ///Looks like crap, mate
        if(ant+i<pts.size() && pts[ant+i].x<=arg.x) {
            if(eq(pts[ant+i].x, arg.x)) {
                if(pts[ant+i].y<=arg.y)
                    ant+=i;
            }
            else
                ant+=i;
        }
    }

    return eq(pts[ant].x, arg.x) && eq(pts[ant].y, arg.y);
}

inline int ctri(int a, int b) {
    PDD tmp;
    int ant;

    ant   = 0;
    tmp.x = (pts[a].x + pts[b].x) * COS + (pts[a].y - pts[b].y) * SIN;
    tmp.y = (pts[b].x - pts[a].x) * SIN + (pts[a].y + pts[b].y) * COS;

    if(gibt(tmp)) ++ant;
    swap(tmp.x, tmp.y);
    if(gibt(tmp)) ++ant;

    return ant;
}

int main(void) {
    ifstream fi("triang.in");
    ofstream fo("triang.out");
    int n, ant;
    f64 x, y;

    ant = 0;

    fi>>n;
    while(n--) {
        fi>>x>>y;
        pts.push_back(PDD(x, y));
    }

    sort(pts.begin(), pts.end());

    for(int i=0;   i<pts.size(); ++i)
    for(int j=i+1; j<pts.size(); ++j)
        ant += ctri(i, j);

    fo<<ant<<'\n';

    fi.close();
    fo.close();
    return 0;
}