Pagini recente » Cod sursa (job #2911026) | Cod sursa (job #1030497) | Cod sursa (job #1349266) | Cod sursa (job #606865) | Cod sursa (job #3165434)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
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]);
}
stack<Point> st;
bool check(Point p3) {
Point p2 = st.top();
st.pop();
Point p1 = st.top();
st.push(p2);
return (getDelta(p1, p2, p3) < 0);
}
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--;
break;
}
}
sort(vp.begin(), vp.end(), [](Point& p1, Point& p2) {
return (getDelta({ xmin,ymin }, p1, p2) > 0);
});
st.push({ xmin,ymin });
st.push({ vp[0].x,vp[0].y });
for (i = 1; i < n; i++) {
while (st.size() >= 2 &&check( vp[i])) {
st.pop();
}
st.push(vp[i]);
}
cout << st.size() << "\n";
cout << fixed << setprecision(12);
while (!st.empty()) {
cout << st.top().x << " " << st.top().y << "\n";
st.pop();
}
return 0;
}