Pagini recente » Cod sursa (job #1739791) | Cod sursa (job #1395047) | Cod sursa (job #2349089) | Cod sursa (job #3163069) | Cod sursa (job #2691305)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 120000;
struct Point {
long double x, y;
bool operator < (const Point other) const {
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int N;
Point v[NMAX + 5];
int vf;
Point st[NMAX + 5];
bool ccw(Point A, Point B, Point C)
{
return (B.y - A.y) * (C.x - A.x) < (C.y - A.y) * (B.x - A.x);
}
inline bool cmp(const Point A, const Point B)
{
return ccw(v[1], A, B);
}
int main()
{
cin >> N;
for(int i = 1; i <= N; i++)
cin >> v[i].x >> v[i].y;
for(int i = 2; i <= N; i++)
if(v[i] < v[1]) swap(v[1], v[i]);
sort(v + 2, v + N + 1, cmp);
for(int i = 1; i <= N; i++) {
while(vf > 1 && !ccw(st[vf - 1], st[vf], v[i]))
vf--;
st[++vf] = v[i];
}
cout << vf << '\n';
for(int i = 1; i <= vf; i++)
cout << fixed << setprecision(12) << st[i].x << ' ' << st[i].y << '\n';
return 0;
}