Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3333183)
#include <fstream>
#include <iomanip>
using namespace std;
struct Punct {
long double x, y;
};
long double cross(const Punct &O, const Punct &A, const Punct &B) {
// (A - O) x (B - O)
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
bool lessPt(const Punct &a, const Punct &b) {
if (a.x < b.x) return true;
if (a.x > b.x) return false;
return (a.y < b.y);
}
bool equalPt(const Punct &a, const Punct &b) {
return (a.x == b.x && a.y == b.y);
}
// MergeSort fără STL
void mergeSort(Punct *v, Punct *tmp, int st, int dr) {
if (st >= dr) return;
int mid = (st + dr) / 2;
mergeSort(v, tmp, st, mid);
mergeSort(v, tmp, mid + 1, dr);
int i = st, j = mid + 1, k = st;
while (i <= mid && j <= dr) {
if (lessPt(v[i], v[j])) tmp[k++] = v[i++];
else tmp[k++] = v[j++];
}
while (i <= mid) tmp[k++] = v[i++];
while (j <= dr) tmp[k++] = v[j++];
for (int t = st; t <= dr; t++) v[t] = tmp[t];
}
int main() {
ifstream fin("HULL.in");
ofstream fout("HULL.out");
int n;
fin >> n;
Punct *p = new Punct[n];
for (int i = 0; i < n; i++) fin >> p[i].x >> p[i].y;
// sortare dupa (x, y)
Punct *tmp = new Punct[n];
mergeSort(p, tmp, 0, n - 1);
delete[] tmp;
// eliminare duplicate (daca exista)
int m = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || !equalPt(p[i], p[m - 1])) p[m++] = p[i];
}
n = m;
if (n == 1) {
fout << 1 << "\n";
fout << fixed << setprecision(6) << (double)p[0].x << " " << (double)p[0].y << "\n";
delete[] p;
return 0;
}
// hull are maxim 2*n puncte
Punct *hull = new Punct[2 * n + 5];
int H = 0;
// LOWER hull (de la stanga la dreapta)
for (int i = 0; i < n; i++) {
while (H >= 2 && cross(hull[H - 2], hull[H - 1], p[i]) <= 0) {
H--;
}
hull[H++] = p[i];
}
// UPPER hull (de la dreapta la stanga)
int lowerSize = H;
for (int i = n - 2; i >= 0; i--) {
while (H > lowerSize && cross(hull[H - 2], hull[H - 1], p[i]) <= 0) {
H--;
}
hull[H++] = p[i];
}
// ultimul punct = primul, il eliminam
if (H > 1) H--;
// afisare in ordine trigonometrica (CCW)
fout << H << "\n";
fout << fixed << setprecision(6);
for (int i = 0; i < H; i++) {
fout << (double)hull[i].x << " " << (double)hull[i].y << "\n";
}
delete[] hull;
delete[] p;
return 0;
}