Pagini recente » Cod sursa (job #3220947) | Cod sursa (job #351308) | Cod sursa (job #432533) | Cod sursa (job #2433931) | Cod sursa (job #1509847)
#include <bits/stdc++.h>
// #define x first
// #define y second
#define VM 120005
#define pb push_back
#define ppb pop_back
#define ll long long
#define pdd pair<double, double>
#define eps 1e-12
using namespace std;
//don't forget to put input in the file!!!
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x,y;
}v[VM], st[VM], st2[VM];
int n, vf, vf2;
double crossProduct(point a, point b, point o){
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;
}
bool cmp(point a, point b){
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
int main(){
f>>n;
for(int i=0; i<n; ++i) f>>v[i].x>>v[i].y;
sort(v, v + n, cmp);
// for(int i=0; i<n; ++i)
// cout<<v[i].x<<' '<<v[i].y<<'\n';
st[++vf] = v[0];
st[++vf] = v[1];
for(int i=2; i<n; ++i){
while(vf >= 2 && crossProduct(st[vf - 1], st[vf], v[i]) < 0)
--vf;
st[++vf] = v[i];
}
st2[++vf2] = v[n - 1];
st2[++vf2] = v[n - 2];
for(int i=n - 3; i>=0; --i){
while(vf2 >= 2 && crossProduct(st2[vf2 - 1], st2[vf2], v[i]) < 0)
--vf2;
st2[++vf2] = v[i];
}
g<<vf + vf2 - 2<<'\n';
for(int i=1; i<=vf; ++i)
g<<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';
for(int i=2; i<vf2; ++i)
g<<fixed<<setprecision(6)<<st2[i].x<<' '<<st2[i].y<<'\n';
return 0;
}