Pagini recente » Cod sursa (job #2474067) | Cod sursa (job #191619) | Cod sursa (job #1101767) | Cod sursa (job #895536) | Cod sursa (job #3165429)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
double xmin = 1000000000.0, ymin;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Point {
double x, y;
};
vector<Point> vp;
double getDelta(Point p1,Point p2,Point p3) {
vector<vector<double>> mat =
{
{p1.x,p1.y,1},
{p2.x,p2.y,1},
{p3.x,p3.y,1},
{p1.x,p1.y,1},
{p2.x,p2.y,1},
};
return mat[0][0] * mat[1][1] * mat[2][2] + mat[1][0] * mat[2][1] * mat[3][2] + mat[2][0] * mat[3][1] * mat[4][2] -
(mat[0][2] * mat[1][1] * mat[2][0] + mat[1][2] * mat[2][1] * mat[3][0] + mat[2][2] * mat[3][1] * mat[4][0]);
}
vector<Point> v1;
int main() {
int i, j, n;
double x, y, nr;
cin >> n;
for (i = 0; i < n; i++) {
cin >> x >> y;
if (xmin > x) {
xmin = x;
ymin = y;
}
vp.push_back({ x,y });
}
for (i = 0; i < n; i++) {
if (vp[i].x == xmin && vp[i].y == ymin) {
vp.erase(vp.begin() + i);
n--;
}
}
sort(vp.begin(), vp.end(), [](Point& p1, Point& p2) {
return (getDelta({ xmin,ymin }, p1,p2) > 0);
});
v1.push_back({ xmin,ymin });
v1.push_back({ vp[0].x,vp[0].y});
for (i = 1; i < n; i++) {
Point p2 = *v1.rbegin();
Point p1 = *(v1.rbegin()+1);
while (vl.size() >= 2 && getDelta(*(v1.rbegin() + 1), *v1.rbegin(), vp[i]) < 0) {
v1.pop_back();
}
v1.push_back(vp[i]);
}
cout << v1.size() << "\n";
cout << fixed <<setprecision(12);
for (auto p : v1) {
cout << p.x << " " << p.y << "\n";
}
return 0;
}