Pagini recente » Cod sursa (job #868456) | Cod sursa (job #3032336) | Cod sursa (job #566261) | Cod sursa (job #1803685) | Cod sursa (job #1846775)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int maxn = 12e4 + 5;
int Stk[maxn], top;
struct Point {
double x, y;
} P[maxn];
inline double Det (const Point& A, const Point& B, const Point& C) {
return A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x;
}
inline bool Cmp (const Point& X, const Point& Y) {
return Det(P[1], X, Y) > 0;
}
int main() {
ios_base :: sync_with_stdio (false);
int n, i, pos = 1;
fin >> n;
for (i = 1; i <= n; i++) {
fin >> P[i].x >> P[i].y;
if (P[i].x < P[pos].x) {
pos = i;
}
if (P[i].x == P[pos].x && P[i].y < P[pos].y) {
pos = i;
}
}
swap(P[1], P[pos]);
sort(P + 2, P + n + 1, Cmp);
P[n + 1] = P[1];
Stk[++top] = 1;
for (i = 2; i <= n; i++) {
Stk[++top] = i;
while (top && Det(P[Stk[top - 1]], P[Stk[top]], P[i + 1]) < 0) {
top--;
}
}
fout << fixed << setprecision(6) << top << "\n";
for (i = 1; i <= top; i++) {
fout << P[Stk[i]].x << " " << P[Stk[i]].y << "\n";
}
fin.close();
fout.close();
return 0;
}