Pagini recente » Cod sursa (job #1446776) | Cod sursa (job #2241040) | Cod sursa (job #3143564) | Cod sursa (job #31016) | Cod sursa (job #2884024)
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double eps = 1.0e-14;
struct puncte
{
double x, y;
};
stack <puncte> st;
puncte p[120005];
// 0 - coliniare
// 1 - counterclockwise
// -1 - clockwise
puncte nexttotop()
{
puncte x = st.top();
st.pop();
puncte y = st.top();
st.push(x);
return y;
}
int ccw(puncte p, puncte q, puncte r)
{
double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if(fabs(val) < eps)
return 0;
if(val >= eps)
return -1;
return 1;
}
double distanta(puncte x, puncte y)
{
return (x.x - y.x) * (x.x - y.x) - (x.y - y.y) * (x.y - y.y);
}
int cmp(puncte x, puncte y)
{
return (ccw(p[0], x, y) < 0);
}
int main()
{
int n, i, j;
cin >> n;
cin >> p[0].x >> p[0].y;
// p[0].x += 1005;
//p[0].y += 1005;
for(i = 1; i < n; i++){
cin >> p[i].x >> p[i].y;
// p[i].x += 1005;
//p[i].y += 1005;
if((p[i].y - p[0].y <= -eps) or (fabs(p[i].y - p[0].y < eps) and p[i].x - p[0].x <= -eps))
swap(p[0], p[i]);
}
sort(p + 1, p + n, cmp);
p[n] = p[0];
st.push(p[0]);
st.push(p[1]);
for(i = 2; i < n; i++){
while(st.size() >= 2 and ccw(nexttotop(), st.top(), p[i]) == 1)
st.pop();
st.push(p[i]);
}
cout << st.size() << "\n";
stack <puncte> afis;
cout << fixed << showpoint;
cout << setprecision(6);
cout << p[0].x << " " << p[0].y << "\n";
while(st.size() > 1){
cout << st.top().x << " " << st.top().y << "\n";
afis.push(st.top());
st.pop();
}
/*while(!afis.empty()){
cout << fixed << showpoint;
cout << setprecision(6);
cout << afis.top().x << " " << afis.top().y << "\n";
afis.pop();
}*/
return 0;
}