Pagini recente » Cod sursa (job #2978586) | Cod sursa (job #2737653) | Cod sursa (job #451081) | Cod sursa (job #234234) | Cod sursa (job #1509823)
#include <bits/stdc++.h>
// #define x first
// #define y second
#define VM 100005
#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;
double crossProduct(int ax, int ay, int bx, int by, int ox, int oy){
ax -= ox;
ay -= oy;
bx -= ox;
by -= oy;
return ax * by - ay * bx;
}
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';
int vf = 0, vf2 = 0;
st[++vf] = v[0];
st[++vf] = v[1];
for(int i=2; i<n; ++i){
while(vf >= 2 && crossProduct(st[vf - 1].x, st[vf - 1].y, st[vf].x, st[vf].y, v[i].x, v[i].y) < 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].x, st2[vf2 - 1].y, st2[vf2].x, st2[vf2].y, v[i].x, v[i].y) < 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;
}