Pagini recente » Cod sursa (job #3179912) | Cod sursa (job #1809144) | Cod sursa (job #791357) | Cod sursa (job #1015627) | Cod sursa (job #3183545)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Point {
double x, y;
};
vector<Point> points;
vector<Point> vp;
Point origin = { INT32_MAX,INT32_MAX };
double compare(Point& p1, Point& p2) {
return p1.x * p2.y - p1.y * p2.x;
}
bool isConvex(Point& p1, Point& p2, Point& p3) {
Point p12 = { p2.x - p1.x,p2.y - p1.y };
Point p23 = { p3.x - p2.x,p3.y - p2.y };
return compare(p12, p23)>0;
}
int main() {
int i, j, nr, n;
double x, y;
cin >> n;
for (i = 0; i < n; i++) {
cin >> x >> y;
if (origin.x > x||(origin.x == x&& origin.y > y)) {
origin = { x,y };
}
points.push_back({ x,y });
}
sort(points.begin(), points.end(), [](Point& p1, Point& p2) {
if (isConvex(origin, p1, p2)) {
return true;
}
else if (isConvex(origin, p2, p1)) {
return false;
}
return (abs(p1.x-origin.x)+ abs(p1.y - origin.y))< (abs(p2.x - origin.x) + abs(p2.y - origin.y));
});
vp.push_back(points[0]);
vp.push_back(points[1]);
i = 2;
while (i < n) {
double val = isConvex(vp[vp.size() - 2], vp[vp.size() - 1], points[i]);
if (isConvex(vp[vp.size() - 2], vp[vp.size() - 1], points[i])) {
vp.push_back(points[i]);
}
else {
vp.pop_back();
vp.push_back(points[i]);
}
i++;
}
if (isConvex(vp[vp.size() - 2], vp[vp.size() - 1],vp[0])) {
vp.pop_back();
}
cout << vp.size() << "\n";
for (auto p : vp) {
cout << fixed<<setprecision(12)<< p.x << " " << p.y<<"\n";
}
return 0;
}