Cod sursa(job #1336795)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 8 februarie 2015 10:22:02
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
#define Nmax 1500
#define EPS 0.001
#define sin60 0.8660254
#define mod(a) ( (a) < 0 ? -(a) : (a) )

struct pct {double x, y;} v[Nmax];

bool CMP(pct p1, pct p2) {return p1.x < p2.x;}
int binary_search(int, int, double) ;

int main()
{
    int i, j, k, n, poz, nr = 0;
    bool gasit;
    
    pct aux;
    
    fin >> n;
    for(i = 0; i < n; ++i) fin >> v[i].x >> v[i].y;
    
    sort(v, v + n, CMP);
    
    for(i = 0; i < n; ++i)
        for(j = i + 1; j < n; ++j)
    {   /* prima solutie */
        //aux = v[i] + (v[j] - v[i]) * deg60;
        aux.x = v[i].x + (v[j].x - v[i].x) / 2 - (v[j].y - v[i].y) * sin60;
        aux.y = v[i].y + (v[j].x - v[i].x) * sin60 + (v[j].y - v[i].y) / 2;
        
        gasit = 0;
        poz = binary_search(j + 1, n - 1, aux.x);
        
        if(poz != -1)
        {
            for(k = poz; k > j && mod(v[k].x - aux.x) < EPS && !gasit; --k)
                if(mod(v[k].y - aux.y) < EPS) gasit = 1;
        
            for(k = poz + 1; k < n && mod(v[k].x - aux.x) < EPS && !gasit; --k)
                if(mod(v[k].y - aux.y) < EPS) gasit = 1;
            
            if(gasit) ++nr;
        }
        
        /* a doua solutie */
        aux.x = v[i].x + (v[j].x - v[i].x) / 2 + (v[j].y - v[i].y) * sin60;
        aux.y = v[i].y - (v[j].x - v[i].x) * sin60 + (v[j].y - v[i].y) / 2;
        
        gasit = 0;
        poz = binary_search(j + 1, n - 1, aux.x);
        
        if(poz != -1)
        {
            for(k = poz; k > j && mod(v[k].x - aux.x) < EPS && !gasit; --k)
                if(mod(v[k].y - aux.y) < EPS) gasit = 1;
            
            for(k = poz + 1; k < n && mod(v[k].x - aux.x) < EPS && !gasit; --k)
                if(mod(v[k].y - aux.y) < EPS) gasit = 1;
            
            if(gasit) ++nr;
        }
    }
    
    fout << nr << '\n';
    return 0;
}


int binary_search(int st, int dr, double val)
{
    if(st > dr) return -1;
    
    int mijl;
    while(st <= dr)
    {
        mijl = (st + dr) >> 1;
        if(mod(val - v[mijl].x) < EPS) return mijl;
        
        if(val < v[mijl].x) dr = st - 1;
        else st = mijl + 1;
    }
    
    return -1;
}