Pagini recente » Monitorul de evaluare | Cod sursa (job #3305514) | Cod sursa (job #3338187) | Cod sursa (job #3306025) | Cod sursa (job #3318856)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdint.h>
#include <algorithm>
const int32_t MAX_N = 120000;
struct Point {
double x, y;
};
Point vec[MAX_N];
int32_t res[MAX_N], top = 0;
double SignedArea(const Point& p1, const Point& p2, const Point& p3) {
return 0.5 * (p1.x * p2.y + p2.x * p3.y + p3.y * p1.x - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x);
}
bool CompPoints(const Point& p1, const Point& p2) {
return SignedArea(vec[0], p1, p2) > 0.0;
}
int main() {
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int32_t n;
fin >> n;
for(int32_t i = 0; i != n; ++i)
fin >> vec[i].x >> vec[i].y;
for(int32_t i = 1; i != n; ++i) {
if(vec[i].x < vec[0].x || (vec[i].x == vec[0].x && vec[i].y < vec[0].y))
std::swap(vec[i], vec[0]);
}
std::sort(vec + 1, vec + n, CompPoints);
res[0] = 0;
res[1] = 1;
top = 2;
for(int32_t i = 2; i != n; ++i) {
while(top >= 2 && SignedArea(vec[res[top - 2]], vec[res[top - 1]], vec[i]) < 0.0)
--top;
res[top++] = i;
}
while(top >= 3 && SignedArea(vec[res[top - 2]], vec[res[top - 1]], vec[res[0]]) < 0.0)
--top;
fout << std::fixed << std::setprecision(6);
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;
}