Pagini recente » Cod sursa (job #1427844) | Cod sursa (job #53083) | Cod sursa (job #177282) | Cod sursa (job #1079755) | Cod sursa (job #2380390)
#include <bits/stdc++.h>
using namespace std;
const int nmax=120005;
struct numere{double x, y;};
numere v[nmax];
deque <numere> st;
deque <numere> dr;
deque <int> coada;
deque <numere> rasp;
bool cmp(numere a, numere b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
short semn(double x1, double y1, double x2, double y2, double x3, double y3)
{
if(x1*y2+x2*y3+x3*y1-y2*x3-y3*x1-y1*x2>=0)
return 1;
return -1;
}
void infasuratoare(int sem)
{
int x1, y1, x2, y2;
x1=v[0].x;
y1=v[0].y;
if(sem==1)
{
x2=dr[0].x;
y2=dr[0].y;
coada.push_back(0);
for(int i=1;i<dr.size();i++)
{
if(semn(x1, y1, dr[i].x, dr[i].y, x2, y2)!=sem)
{
x1=x2;y1=y2;
x2=dr[i].x;y2=dr[i].y;
coada.push_back(i);
}else
{
x2=dr[i].x;y2=dr[i].y;
coada.pop_back();
coada.push_back(i);
}
}
}
else
{
x2=st[0].x;
y2=st[0].y;
coada.push_back(0);
for(int i=1;i<dr.size();i++)
{
if(semn(x1, y1, st[i].x, st[i].y, x2, y2)!=sem)
{
x1=x2;y1=y2;
x2=st[i].x;y2=st[i].y;
coada.push_back(i);
}else
{
x2=st[i].x;y2=st[i].y;
coada.pop_back();
coada.push_back(i);
}
}
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%lf%lf", &v[i].x, v[i].y);
sort(v+1, v+n+1, cmp);
for(int i=2;i<n;i++)
{
if(semn(v[0].x, v[0].y, v[i].x, v[i].y, v[n].x, v[n].y)==1)
dr.push_back(v[i]);
else
st.push_back(v[i]);
}
rasp.push_back(v[0]);
infasuratoare(1);
while(coada.size())
{
rasp.push_back(dr[coada.front()]);
coada.pop_front();
}
infasuratoare(-1);
while(coada.size())
{
rasp.push_back(st[coada.back()]);
coada.pop_back();
}
rasp.push_back(v[n]);
printf("%d\n", rasp.size());
for(int i=0;i<rasp.size();i++)
printf("%lf %lf\n", rasp[i].x, rasp[i].y);
return 0;
}