Cod sursa(job #1336223)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 7 februarie 2015 10:56:05
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 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) ;
pct operator +(pct a, pct b) {a.x += b.x; a.y += b.y; return a;}
pct operator -(pct a, pct b) {a.x -= b.x; a.y -= b.y; return a;}
pct operator *(pct a, pct b)
    {pct c; c.x = a.x * b.x - a.y * b.y; c.y = a.x * b.y + a.y * b.x; return c;}

int main()
{
    int i, j, k, n, poz, nr = 0;
    bool gasit;
    
    pct deg60, aux;
    deg60.x = 0.5; deg60.y = sin60;
    
    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;
        
        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 = v[i] + v[j] - aux;
        
        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;
}