Cod sursa(job #1777083)

Utilizator MateiMCCiurezu Matei MateiMC Data 12 octombrie 2016 01:28:21
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#define DIST 1124255
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
int n, cautat[DIST][1505][1505], distanta=0;
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=0;
    while(i<v.size()){

        while(v[i].first==v[i+1].first){
            //distanta egala
            if(cautat[distanta][v[i].second.first][v[i].second.second]==1){
                nr_triunghiuri++;
                cautat[distanta][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){
                if(cautat[distanta][v[i].second.first][v[i].second.second]==1){
                    nr_triunghiuri++;
                    cautat[distanta][v[i].second.first][v[i].second.second]=0;
                }
                for(long k1=start; k1<=i; k1++){
                    for(long k2=k1+1; k2<=i+1; k2++){
                        cautat[distanta][v[k1].second.second][v[k2].second.second]=1;
                    }

                }
                i++;
            }

            if(cautat[distanta][v[i].second.first][v[i].second.second]==1){
                nr_triunghiuri++;
                cautat[distanta][v[i].second.first][v[i].second.second]=0;
            }

            i++;

            if(v[i].first==v[i-1].first){
                if(cautat[distanta][v[i].second.first][v[i].second.second]==1){
                    nr_triunghiuri++;
                    cautat[distanta][v[i].second.first][v[i].second.second]=0;
                }
            }

        }
        i++;
        distanta++;
    }

    fout<<nr_triunghiuri;
    return 0;
}