Pagini recente » Cod sursa (job #675313) | Cod sursa (job #899811) | Cod sursa (job #523260) | Cod sursa (job #7611) | Cod sursa (job #3300983)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <stack>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double etalon_x, etalon_y;
struct Point {
double x, y;
bool operator<(const Point& b) const {
double dx1 = x - etalon_x;
double dy1 = y - etalon_y;
double dx2 = b.x - etalon_x;
double dy2 = b.y - etalon_y;
double cross = dx1 * dy2 - dy1 * dx2;
if (cross != 0)
return cross > 0;
double d1 = dx1 * dx1 + dy1 * dy1;
double d2 = dx2 * dx2 + dy2 * dy2;
return d1 < d2;
}
};
Point p[120005];
int n, indice;
int convexitate(const Point& a, const Point& b, const Point& c) {
double dx1 = b.x - a.x;
double dy1 = b.y - a.y;
double dx2 = c.x - a.x;
double dy2 = c.y - a.y;
double cross = dx1 * dy2 - dy1 * dx2;
return cross > 0;
}
int main() {
fin>>n;
etalon_x = 1e308;
etalon_y = 1e308;
for (int i = 0; i < n; ++i) {
fin>>p[i].x>>p[i].y;
if (p[i].x < etalon_x || (p[i].x == etalon_x && p[i].y < etalon_y)) {
etalon_x = p[i].x;
etalon_y = p[i].y;
indice = i;
}
}
swap(p[0],p[indice]);
sort(p+1,p+n);
stack<Point> stiva,stiva2;
stiva.push(p[0]);
stiva.push(p[1]);
for (int i = 2; i < n; ++i) {
while (stiva.size() >= 2) {
Point p1 = stiva.top();
stiva.pop();
Point p2 = stiva.top();
if (convexitate(p2, p1, p[i])) {
stiva.push(p1);
break;
}
}
stiva.push(p[i]);
}
fout << stiva.size() << "\n" << setprecision(6) << fixed;
while (!stiva.empty()) {
Point p2 = stiva.top();
stiva.pop();
stiva2.push(p2);
}
//afisare- stiva strica ordinea
while (!stiva2.empty()) {
Point p3 = stiva2.top();
stiva2.pop();
fout << p3.x << " " << p3.y << "\n";
}
return 0;
}