Pagini recente » Cod sursa (job #2241214) | Cod sursa (job #409746) | Cod sursa (job #1738442) | Cod sursa (job #1173845) | Cod sursa (job #1497696)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define s second
#define f first
#define pub push_back
#define pob pop_back
using namespace std;
const int nmx = 120002;
int n;
pair <double,double> p[nmx];
vector <int> sus,jos;
int determinant(int p1, int p2, int p3) {
return (((p[p2].f-p[p1].f)*(p[p3].s-p[p1].s))-((p[p3].f-p[p1].f)*(p[p2].s-p[p1].s))) >= 0 ? 1 : -1;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].f, &p[i].s);
sort(p+1,p+n+1);
sus.pub(1);
sus.pub(2);
jos.pub(1);
jos.pub(2);
int s = 2, j = 2;
for(int i = 3; i <= n; ++i) {
while(s >= 2 && determinant(sus[s-2],sus[s-1],i) == 1) {
sus.pob();
-- s;
}
sus.pub(i);
++ s;
while(j >= 2 && determinant(jos[j-2],jos[j-1],i) == -1) {
jos.pob();
-- j;
}
jos.pub(i);
++ j;
}
int sum = s + j;
if(jos[0] == sus[0]) {
-- sum;
jos[0] = -1;
}
if(jos[j-1] == sus[s-1]) {
-- sum;
sus[s-1] = -1;
}
printf("%d\n", sum);
for(int i = 0; i < j; ++i)
if(jos[i] >= 0)
printf("%lf %lf\n", p[jos[i]].f, p[jos[i]].s);
for(int i = s - 1; i >= 0 ; --i)
if(i >= 0 && sus[i] >= 0)
printf("%lf %lf\n", p[sus[i]].f, p[sus[i]].s);
return 0;
}