Cod sursa(job #31043)

Utilizator varuvasiTofan Vasile varuvasi Data 15 martie 2007 13:36:05
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#include <vector>
#include <map>
#include <cmath>

#define MAX 1505
#define EPS 0.001
#define eps 0.001

using namespace std;

struct punct {
    double xx, yy;
} pp[MAX];   

map<double, pair<int, int> > memo;
map<double, pair<int, int> >::iterator it;
vector<vector<map<int, bool> > > foundu;

double aux, d[MAX][MAX];
int n, rez;

double dist(double x1, double y1, double x2, double y2);

int main()
{
    FILE *fin = fopen("triang.in", "r");
    fscanf(fin, "%d", &n);
    for (int i = 1; i <= n; ++i)
        fscanf(fin, "%lf%lf", &pp[i].xx, &pp[i].yy);    
    fclose(fin);
    
    foundu.resize(n+6);
    for (int i = 0; i <= n+2; ++i)
        foundu[i].resize(n+6);
    
    for (int i = 1; i <= n; ++i)
        for (int j = i+1; j <= n; ++j)
        {
            d[i][j]= dist(pp[i].xx, pp[i].yy, pp[j].xx, pp[j].yy);
            memo[d[i][j]] = make_pair(i, j);
        }    
    int k;
    for (int i = 1; i <= n; ++i)
        for (int j = i+1; j <= n; ++j)
        {
            it = memo.lower_bound(d[i][j]-EPS);
            while (abs((*it).first - d[i][j]) < eps)
            {
                k = (*it).second.second;
                if (!foundu[i][j].count(k) && i != j && i != k && j != k)
                    rez++;
                foundu[i][j][k] = true;
                foundu[i][k][j] = true;
                foundu[j][i][k] = true;
                foundu[j][k][i] = true;
                foundu[k][i][j] = true;
                foundu[k][j][i] = true;
                it++;
            }    
        }        

    FILE *fout = fopen("triang.out", "w");
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    
    return 0;
}    

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
}