Pagini recente » Utilizatori inregistrati la FMI No Stress 2017 | Cod sursa (job #3134961) | Cod sursa (job #655176) | Cod sursa (job #1307413) | Cod sursa (job #2383635)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct
{
double x, y;
}st[120001], vs[120001], vd[120001];
int det(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
bool cmp(punct a, punct b)
{
if(a.y<b.y)
return true;
else if(a.y>b.y)
return false;
else
{
if(a.x<b.x)
return true;
return false;
}
}
int main()
{
int n, nrs = 1, nrd = 1;
in>>n;
for(int i = 1; i<=n; i++)
{
in>>st[i].x>>st[i].y;
}
sort(st+1, st+n+1, cmp);
int c = 2;
vs[1] = st[1];
vd[1] = st[1];
while(c != n)
{
if(det(st[1], st[n], st[c])<0)
{
while(nrd>2 && det(vd[nrd-1], vd[nrd], st[c])<0)
--nrd;
vd[++nrd] = st[c];
}
else
{
while(nrs>2 && det(vs[nrs-1], vs[nrs], st[c])>0)
--nrs;
vs[++nrs] = st[c];
}
c++;
}
vd[++nrd] = st[n];
out<<nrs+nrd-1<<'\n';
for(int i = 1; i<=nrd; i++)
out<<fixed<<setprecision(6)<<vd[i].x<<" "<<vd[i].y<<'\n';
for(int i = nrs; i>=2; i--)
out<<fixed<<setprecision(6)<<vs[i].x<<" "<<vs[i].y<<'\n';
return 0;
}