Pagini recente » Cod sursa (job #2694728) | Cod sursa (job #2391267) | Cod sursa (job #2707227) | Cod sursa (job #500956) | Cod sursa (job #2207932)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define dMAX 120000
using namespace std;
int n, pos = 1, h;
typedef pair<double, double> Point;
Point arr[dMAX + 2], myStack[dMAX + 2];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double CrossProduct(Point e1, Point e2, Point e3) {
return (e2.x - e1.x) * (e3.y - e1.y) - (e2.y - e1.y) * (e3.x - e1.x);
}
bool Compare(Point e1, Point e2) {
return CrossProduct(arr[1], e1, e2) < 0;
}
int main() {
int i, j;
fin >> n;
fin >> arr[1].x >> arr[1].y;
for (i = 2; i <= n; i++) {
fin >> arr[i].x >> arr[i].y;
if (arr[i] < arr[pos]) pos = i;
}
swap(arr[1], arr[pos]);
sort(arr + 2, arr + n + 1, Compare);
myStack[++h] = arr[1];
myStack[++h] = arr[2];
for (i = 3; i <= n; i++) {
while (h >= 2 && CrossProduct(myStack[h - 1], myStack[h], arr[i]) > 0)
h--;
myStack[++h] = arr[i];
}
fout << h << '\n';
for (i = h; i >= 1; i--) {
fout << setprecision(9) << fixed << myStack[i].x << ' ' << myStack[i].y << '\n';
}
}