Cod sursa(job #1777101)

Utilizator MateiMCCiurezu Matei MateiMC Data 12 octombrie 2016 02:41:28
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
int n, cautat[1505][1505], distanta=1;
long nr_triunghiuri=0;
vector< pair< double, pair<int,int> > >v;

struct punct{
    double x,y;
};
punct p[1505];

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>p[i].x>>p[i].y;
    }
    
    for(int i=1; i<=n-1; i++){
        for(int j=i+1; j<=n; j++){
            double distanta = (double)( pow(p[i].x-p[j].x, 2) + pow(p[i].y-p[j].y, 2) );
            double distanta_aprox = round(1000*distanta)/1000;
            
            v.push_back(make_pair(distanta_aprox, make_pair(i,j)));
        }
    }
    
    sort(v.begin(), v.end());

    long i=1;
    while(i<v.size()){
        
        while(v[i].first==v[i-1].first && i<v.size()){
            //distanta egala
            if(cautat[v[i].second.first][v[i].second.second]==distanta){
                nr_triunghiuri++;
                cautat[v[i].second.first][v[i].second.second]=0;
            }
            
            long start=i;
            while(v[i].second.first==v[i-1].second.first && v[i].first==v[i-1].first && i<v.size()){
                
                for(long k1=start; k1<=i-1; k1++){
                    for(long k2=k1+1; k2<=i; k2++){
                        cautat[v[k1].second.second][v[k2].second.second]=distanta;
                    }
                    
                }
                i++;
                if(cautat[v[i].second.first][v[i].second.second]==distanta){
                    nr_triunghiuri++;
                    cautat[v[i].second.first][v[i].second.second]=0;
                }
            }
            
            
            i++;
            
            if(v[i].first==v[i-1].first){
                if(cautat[v[i].second.first][v[i].second.second]==distanta){
                    nr_triunghiuri++;
                    cautat[v[i].second.first][v[i].second.second]=0;
                }
            }
            
        }
        i++;
        distanta++;
    }
    
    fout<<nr_triunghiuri;
    return 0;
}