Mai intai trebuie sa te autentifici.

Cod sursa(job #1525766)

Utilizator cristina_borzaCristina Borza cristina_borza Data 15 noiembrie 2015 16:02:18
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <fstream>
#include <map>

using namespace std;

ifstream f("trapez.in");
ofstream g("trapez.out");

int n , x , y , aux1[1005] , aux2[1005] , nm1 , nm2 , sol1 , sol2 , nr , rep;

pair <int , int> a[1005];

map <int , int> v1 , v2;
map <pair <int , int> , int> mat;

int main() {
    f >> n;

    for(int i = 1 ; i <= n ; ++i) {
        f >> x >> y;
        mat[make_pair(x , y)] = 1;
        v1[x]++;
        v2[y]++;

        a[i].first = x;
        a[i].second = y;
    }

    for(map<int , int> :: iterator it = v1.begin() ; it != v1.end() ; ++it) {
        aux1[++nr] = it->second;
    }

    for(int i = 1 ; i <= nr ; ++i) {
        if(aux1[i] > 1) {
            nm1 = (aux1[i] * (aux1[i] - 1)) / 2;
            for(int j = i + 1 ; j <= nr ; ++j) {
                if(aux1[j] > 1) {
                    nm2 = (aux1[j] * (aux1[j] - 1)) / 2;
                    sol1 += nm1 * nm2;
                }
            }
        }
    }

    nr = 0;

    for(map<int , int> :: iterator it = v2.begin() ; it != v2.end() ; ++it) {
        aux2[++nr] = it->second;
    }

    for(int i = 1 ; i <= nr ; ++i) {
        if(aux2[i] > 1) {
            nm1 = (aux2[i] * (aux2[i] - 1)) / 2;
            for(int j = i + 1 ; j <= nr ; ++j) {
                if(aux2[j] > 1) {
                    nm2 = (aux2[j] * (aux2[j] - 1)) / 2;
                    sol2 += nm1 * nm2;
                }
            }
        }
    }

    for(int i = 1 ; i <= n ; ++i) {
        for(int j = 1 ; j <= n ; ++j) {
            if(a[i].first != a[j].first && a[i].second != a[j].second) {
                if(mat[make_pair(a[i].first ,a[j].second)] == 1 && mat[make_pair(a[j].first ,a[i].second)] == 1) {
                    ++rep;
                }
            }
        }
    }

    g << sol1 + sol2 - rep / 4;
    return 0;
}