Pagini recente » Cod sursa (job #3178871) | Cod sursa (job #1241800) | Cod sursa (job #1966317) | Cod sursa (job #34322) | Cod sursa (job #1116783)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#define N_MAX 120010
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N, x[N_MAX], y[N_MAX], ymin, nr = 1;
struct p {
double x, y;
};
p v[100001], st[N_MAX/100], o = v[0];
bool cross(p a, p b, p c)
{
return ((a.x-c.x) * (b.y-c.y) - (a.y-c.y) * (b.x-c.x) >= 0);
}
bool cmp(p a, p b)
{
return cross(a, b, o);
}
int main()
{
in >> N;
for(int i = 0; i < N; i++)
{
in >> v[i].x >> v[i].y;
//cout << v[i].x << v[i].y;
if(v[i].y < v[ymin].y) ymin = i;
}
v[0] = v[ymin];
sort(v, v + N, cmp);
/*for(int i = 0; i < N; i++)
cout << v[i].x << v[i].y << endl;*/
st[0] = v[0];
for(int i = 1; i < N; i++)
{
while(cross(v[i], st[nr], st[nr - 1]) && nr >= 1)
{
//cout << v[i].x << v[i].y << st[nr].x << st[nr].y << endl;
nr--;
}
//cout << v[i].x << v[i].y << endl;
st[++nr] = v[i];
}
out << nr + 1<< '\n';
out << setprecision(15);
for(int i = 0; i <= nr; i++)
out << st[i].x << " " << st[i].y << endl;
return 0;
}