Pagini recente » Cod sursa (job #2953191) | Cod sursa (job #2349670) | Cod sursa (job #2692216) | Cod sursa (job #52531) | Cod sursa (job #3221439)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdint.h>
#include <algorithm>
const int32_t MAX_N = 120000;
struct Pos {
double x;
double y;
};
Pos vec[MAX_N];
int32_t res[MAX_N], top;
double Area(const Pos& pos1, const Pos& pos2, const Pos& pos3) {
return (pos1.x * pos2.y + pos2.x * pos3.y + pos3.x * pos1.y) - (pos1.y * pos2.x + pos2.y * pos3.x + pos3.y * pos1.x);
}
bool Compare(const Pos& pos1, const Pos& pos2) {
return Area(vec[0], pos1, pos2) > 0;
}
int main() {
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
fout << std::fixed << std::setprecision(6);
int32_t n;
fin >> n;
for(int32_t i = 0; i != n; ++i)
fin >> vec[i].x >> vec[i].y;
int32_t minPos = 0;
for(int32_t i = 1; i != n; ++i)
if(vec[i].x < vec[minPos].x || (vec[i].x == vec[minPos].x && vec[i].y < vec[minPos].y))
minPos = i;
std::swap(vec[0], vec[minPos]);
std::sort(vec + 1, vec + n, Compare);
res[0] = 0;
res[1] = 1;
top = 2;
for(int32_t i = 0; i != n; ++i) {
for(; top != 1 && Area(vec[res[top - 2]], vec[res[top - 1]], vec[i]) <= 0; --top);
res[top++] = i;
}
fout << top << '\n';
for(int32_t i = 0; i != top; ++i)
fout << vec[res[i]].x << ' ' << vec[res[i]].y << '\n';
fin.close();
fout.close();
return 0;
}