Pagini recente » Cod sursa (job #2795161) | Cod sursa (job #1912493) | Cod sursa (job #711813) | Cod sursa (job #1378604) | Cod sursa (job #1509796)
#include <bits/stdc++.h>
#define VM 120005
#define x first
#define y second
#define pdd pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
int vf1, vf2;
pdd p[VM];
pdd stiva1[VM];
pdd stiva2[VM];
bool cmp(pdd a, pdd b){
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double cross_product(pdd o, pdd a, pdd b){
a.x -= o.x;
a.y -= o.y;
b.x -= o.x;
b.y -= o.y;
return a.x * b.y - a.y * b.x;
}
int main()
{
f>>n;
for(int i = 0 ; i < n ; ++i)
f>>p[i].x>>p[i].y;
sort(p , p + n , cmp);
stiva1[++vf1] = p[0];
stiva1[++vf1] = p[1];
for(int i = 2 ; i < n ; ++i){
while(vf1 >= 2 && cross_product(stiva1[vf1 - 1] , stiva1[vf1] , p[i]) < 0)
--vf1;
stiva1[++vf1] = p[i];
}
stiva2[++vf2] = p[n - 1];
stiva2[++vf2] = p[n - 2];
for(int i = n - 3 ; i >= 0 ; --i){
while(vf2 >= 2 && cross_product(stiva2[vf2 - 1] , stiva2[vf2] , p[i]) < 0)
--vf2;
stiva2[++vf2] = p[i];
}
g<<vf1 + vf2 - 2<<'\n';
for(int i = 1 ; i <= vf1 ; ++i)
g<<fixed<<setprecision(6)<<stiva1[i].x<<' '<<stiva1[i].y<<'\n';
for(int i = 2 ; i < vf2 ; ++i)
g<<fixed<<setprecision(6)<<stiva2[i].x<<' '<<stiva2[i].y<<'\n';
return 0;
}