Pagini recente » Cod sursa (job #1783450) | Cod sursa (job #2571791) | Cod sursa (job #2023378) | Cod sursa (job #1738103) | Cod sursa (job #1974445)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
/**
A.x A.y 1
B.x B.y 1
C.x C.y 1
B.x - A.x B.y - A.y
C.x - A.x C.y - A.y
(B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y)
*/
struct Point{
double x,y;
Point():x(0),y(0){};
Point(double _x, double _y): x(_x), y(_y) {}
bool operator < (const Point p) {
if(x < p.x) return true;
if(x == p.x && y < p.y) return true;
return false;
}
};
double det(Point A, Point B, Point C) {
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
const int Nmax = 125005;
Point Stack[Nmax];
int vf;
int N;
vector<Point> v;
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for(int i = 1; i <= N; ++i) {
double x,y;
scanf("%lf%lf", &x, &y);
v.push_back(Point(x,y));
}
sort(v.begin(), v.end());
Point st = v[0];
Point dr = v.back();
Stack[++vf] = st;
for(int i = 1; i <= N; ++i)
if(det(st, dr, v[i]) >= 0)
{
while(vf >= 2 && det(Stack[vf-1], Stack[vf], v[i]) >= 0)
--vf;
Stack[++vf] = v[i];
}
for(int i = N - 1; i >= 0; --i)
if(det(st, dr, v[i]) <= 0)
{
while(vf >= 2 && det(Stack[vf-1], Stack[vf], v[i]) >= 0)
--vf;
Stack[++vf] = v[i];
}
printf("%d\n", vf - 1);
while(vf > 1) {
printf("%.6f %.6f\n", Stack[vf].x, Stack[vf].y);
--vf;
}
return 0;
}