Pagini recente » Cod sursa (job #234466) | Cod sursa (job #1781237) | Cod sursa (job #169844) | Arhiva de probleme | Cod sursa (job #1075543)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
typedef pair<double, double> Point;
const int MAX_N = 120100;
int N;
Point points[MAX_N];
Point hull[MAX_N];
int head;
void read_input();
void solve();
void print_output();
inline double cross_product(const Point &A, const Point &B, const Point &O) {
return ((A.x - O.x) * (B.y - O.y)) - ((A.y - O.y) * (B.x - O.x));
}
int main() {
read_input();
solve();
print_output();
return 0;
}
void read_input() {
fin >> N;
for (int i = 1; i <= N; i += 1) {
fin >> points[i].x >> points[i].y;
}
}
void solve() {
int pos = 1;
for (int i = 2; i <= N; i += 1) {
if (points[i] < points[pos]) {
pos = i;
}
}
swap(points[1], points[pos]);
Point low = points[1];
sort(points + 2, points + N + 1,
[low](const Point &a, const Point &b) {
return cross_product(a, b, low) > 0;
}
);
head = 0;
hull[++head] = points[1];
for (int i = 2; i <= N; i += 1) {
while (head > 2 && cross_product(points[i], hull[head], hull[head - 1]) > 0) {
head -= 1;
}
hull[++head] = points[i];
}
}
void print_output() {
fout << head << '\n';
fout << setprecision(15);
for (int i = 1; i <= head; i += 1) {
fout << hull[i].x << ' ' << hull[i].y << '\n';
}
}