Pagini recente » Cod sursa (job #3254156) | Cod sursa (job #3036470) | Cod sursa (job #3233870) | Cod sursa (job #2588422) | Cod sursa (job #2628250)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point {
double x, y;
};
point v[120005];
int h[120005];
point ll;
const double eps = 1e-12;
double cp(point p1, point p2, point p3) {
return (p2.x - p1.x)*(p3.y - p2.y) - (p2.y - p1.y)*(p3.x - p2.x);
}
bool cmp(point a, point b) {
if(cp(ll, a, b) > 0)
return 1;
if(fabs(cp(ll, a, b)) <= eps)
return (a.x*a.x + a.y*a.y) < (b.x*b.x+b.y*b.y);
return 0;
}
int main()
{
int n;
cin >> n;
ll.x = 1e10;
ll.y = 1e10;
for(int i = 1; i <= n; i++) {
cin >> v[i].x >> v[i].y;
if(v[i].y == ll.y && v[i].x < ll.x)
ll = v[i];
if(v[i].y < ll.y)
ll = v[i];
}
v[0] = ll;
//cout << ll.x << " " << ll.y << endl << endl;
int ok = 0;
for(int i = 1; i <= n; i++) {
if(v[i].x == ll.x && v[i].y == ll.y)
ok = 1;
if(ok)
v[i] = v[i+1];
}
v[n] = ll;
sort(v + 1, v + n, cmp);
int top = 1;
h[0] = 0;
h[1] = 1;
//cout << "HERE";
int i = 2;
while(i <= n) {
if(cp(v[h[top-1]], v[h[top]], v[i]) >= 0) {
h[++top] = i;
i++;
}
else
top--;
}
//top++;
cout << top << endl;
for(int i = 0; i < top; i++) {
cout << v[h[i]].x << " " << v[h[i]].y << endl;
}
//sort()
}