Pagini recente » Cod sursa (job #1415466) | Cod sursa (job #2033976) | Cod sursa (job #1730344) | Cod sursa (job #2002610) | Cod sursa (job #1730249)
#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;
}