Cod sursa(job #1730249)

Utilizator vladc096Vlad Cincean vladc096 Data 16 iulie 2016 17:06:25
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>

using namespace std;

void merge(long arr[], int l, int m, int r) {
	int i, j, k;
	int n1 = m - l + 1;
	int n2 = r - m;
	int* L, *R;

	L = new int[n1];
	R = new int[n2];

	// copy data
	for (i = 0; i < n1; i++) {
		L[i] = arr[l + i];
	}
	for (j = 0; j < n2; j++) {
		R[j] = arr[m + 1 + j];
	}

	// merge L[0..n1], R[0..n2] into arr[l..r]
	i = 0; j = 0; k = l;

	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k++] = L[i++];
		}
		else {
			arr[k++] = R[j++];
		}
	}
	
	while (i < n1) {
		arr[k++] = L[i++];
	}
	
	while (j < n2) {
		arr[k++] = R[j++];
	}

	// free memory(L[] and R[])
	delete[] L;
	delete[] R;
}

void mergeSort(long arr[], int l, int r) {
	if (l >= r)
		return;

	// middle position (divide)
	int m = (l + r) / 2;

	// sort the first half (conquer)
	mergeSort(arr, l, m);

	// sort the second half (conquer)
	mergeSort(arr, m + 1, r);

	// (combine)
	merge(arr, l, m, r);
}

void sort(long arr[], int size) {
	return mergeSort(arr, 0, size - 1);
}

int main() {
	int n;
	long* x;
	long* y;
	int nrTx, nrTy;

	// input
	ifstream f("trapez.in");
	f >> n;
	x = new long[n];
	y = new long[n];
	for (int i = 0; i < n; i++) {
		f >> x[i] >> y[i];
	}
	f.close();

	// sort
	sort(x, n);
	sort(y, n);

	// count nrT
	nrTx = 0; nrTy = 0;

	for (int i = 1; i < n; i++) {
		if (x[i - 1] == x[i]) {
			nrTx++;
		}
	}
	nrTx /= 2;

	for (int j = 1; j < n; j++) {
		if (y[j - 1] == y[j]) {
			nrTy++;
		}
	}
	nrTy /= 2;

	// free memory
	delete[] x;
	delete[] y;

	// output
	ofstream g("trapez.out");
	g << static_cast<int>(nrTx + nrTy) << "\n";
	g.close();

	return 0;
}