Cod sursa(job #1255761)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 5 noiembrie 2014 08:44:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#define error 0.0001
#define rad3pe2 sqrt(3) / 2
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");

int n, i, j, sol;
double x_sol, y_sol, D;
struct tri {
    double x, y;
}A[10100];
int cmp(tri a, tri b){
    if(a.x < b.x)
        return 1;
    if(a.x == b.x)
        if(a.y < b.y)
            return 1;
}
double modul(double x){
    if(x < 0)
        return -x;
    return x;
}
//double distanta(double x1, double y1, double x2, double y2){
  //  return sqrt((x2 - x1) * (x2 - x1) +  (y2 - y1) * (y2 - y1));
//}
//void distanta_punct_dreapta(){
    //modul((ax + by +c) / sqrt(a * a + b * b)

//}
void cautare_binara(double x, double y){
    int st = j + 1;
    int dr = n;
    int mid = 0;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(A[mid].x + error > x)
            dr = mid - 1;
        else
            if( A[mid].x + error < x)
                st = mid + 1;
            else
                if(A[mid].y +error < y)
                    st = mid + 1;
                else
                    dr = mid - 1;
    }
    if(modul(x - A[st].x) < error && modul(y - A[st].y) < error)
        sol ++;
}
int main()
{
    fin >> n;
    for(i = 1; i <= n; i ++)
        fin >> A[i].x >> A[i].y;
    sort(A + 1, A + n + 1, cmp);
    for(i = 1; i <= n - 2; i ++)
        for(j = i + 1; j <= n - 1; j ++){
           // D = distanta(A[i].x, A[i].y, A[j].x, A[j].y);
           // x_mid = A[i].x + modul(A[i].x-A[j].x) / 2;
           // y_mid = A[i].y + modul(A[i].y-A[j].y) / 2;
           // D_i_mid = D / 2;
           // D_i_mid_sol = sqrt(D * D - D_i_mid * D_i_mid);
           // distanta_punct_dreapta(D_i_mid_sol);
            x_sol = (A[i].x + A[j].x) / 2 + rad3pe2 * (A[i].y - A[j].y);
            y_sol = (A[i].y + A[j].y) / 2 + rad3pe2* (A[j].x - A[i].x);
            cautare_binara(x_sol, y_sol);
            x_sol = (A[i].x + A[j].x) / 2 + rad3pe2* (A[j].y - A[i].y);
            y_sol = (A[i].y + A[j].y) / 2 + rad3pe2* (A[i].x - A[j].x);
            cautare_binara(x_sol, y_sol);
        }
    fout << sol;
    return 0;
}