Pagini recente » Cod sursa (job #471794) | Cod sursa (job #2187657) | Cod sursa (job #549353) | Cod sursa (job #1878860) | Cod sursa (job #1919315)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int maxn = 12e4 + 5;
pair <double,double> P[maxn];
int Stk[maxn], top;
inline double Det (pair <double,double> A, pair <double,double> B, pair <double,double> C) {
return A.first * B.second + B.first * C.second + C.first * A.second - A.second * B.first - B.second * C.first - C.second * A.first;
}
inline bool Cmp (pair <double,double> A, pair <double,double> B) {
return Det (P[1], A, B) > 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].first >> P[i].second;
if (P[i].first < P[pos].first) {
pos = i;
} else if (P[i].first == P[pos].first && P[i].second < P[pos].second) {
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 > 0 && 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]].first << " " << P[Stk[i]].second << "\n";
}
return 0;
}