Pagini recente » Cod sursa (job #2101388) | Cod sursa (job #378478) | Cod sursa (job #2701341) | Cod sursa (job #330266) | Cod sursa (job #2957284)
#include <bits/stdc++.h>
#define NMAX 120000
#define XYMAX 1000000000
#define CW -1
#define COL 0
#define CCW 1
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
double x, y;
bool operator == (const punct &A) const {
return (A.x == x && A.y == y);
}
};
punct lowest;
punct v[NMAX + 1];
int get_orientation(punct A, punct B, punct C) {
long double val = (long double)(B.y - A.y) * (C.x - B.x) - (long double)(B.x - A.x) * (C.y - B.y);
if (val < 0)
return CCW;
else if (val == 0)
return COL;
else
return CW;
}
bool cmp(punct A, punct B) {
if (A == lowest)
return 1;
if (B == lowest)
return 0;
/// le sortez astfel incat lowest sa fie primul
return get_orientation(lowest, A, B) == CCW;
}
int main() {
int n, i;
fin >> n;
lowest.x = lowest.y = XYMAX + 1;
for (i = 0; i < n; i++) {
fin >> v[i].x >> v[i].y;
if (v[i].x < lowest.x || (v[i].x == lowest.x && v[i].y < lowest.y))
lowest.x = v[i].x, lowest.y = v[i].y;
}
sort(v, v + n, cmp);
vector < punct > stiva;
stiva.push_back( lowest );
for (i = 1; i < n; i++) {
while (stiva.size() > 1 && get_orientation(stiva[stiva.size() - 2], stiva.back(), v[i]) == CW)
stiva.pop_back();
stiva.push_back(v[i]);
}
fout << stiva.size() << "\n";
for (i = 0; i < stiva.size(); i++) {
fout << fixed << setprecision(6) << (double)stiva[i].x << " " << (double)stiva[i].y << "\n";
}
return 0;
}