Pagini recente » Cod sursa (job #3142366) | Cod sursa (job #2768332) | Cod sursa (job #3182237) | Cod sursa (job #2119459) | Cod sursa (job #2208813)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct puncte
{
double x, y;
/// dreapta=1 si stanga=2
int position;
}v[100001];
inline bool sortingParameter(puncte a, puncte b)
{
return a.y<b.y || ( a.y==b.y && a.x<b.x );
}
double checkWay(int p, int p1, int p2)
{
return v[p1].x*v[p2].y + v[p2].x*v[p].y + v[p].x*v[p1].y - v[p].x*v[p2].y - v[p1].x*v[p].y -v[p2].x*v[p1].y;
}
int n, stack1[100001], stack2[100001];
int main()
{
in>>n;
for(register int i=1; i<=n; ++i)
in>>v[i].x>>v[i].y;
sort(v+1, v+n+1, sortingParameter);
for(register int i=2; i<n; ++i)
if(checkWay(i, 1, n)<0)
v[i].position=1;
else
v[i].position=2;
int k=0;
stack1[++k]=1;
for(register int i=2; i<n; ++i)
{
if(k>=2 && v[i].position==1 && checkWay(i, stack1[k-1], stack1[k])>0)
stack1[++k]=i;
else if(k>=2 && v[i].position==1 && checkWay(i, stack1[k-1], stack1[k])<0)
stack1[k]=i;
else if(v[i].position==1 && k==1)
stack1[++k]=i;
}
stack1[++k]=n;
int k2=0;
stack2[++k2]=1;
for(register int i=2; i<n; ++i)
{
if(k>=2 && v[i].position==2 && checkWay(i, stack2[k2-1], stack2[k2])<0)
stack2[++k2]=i;
else if(k>=2 && v[i].position==2 && checkWay(i, stack2[k2-1], stack2[k2])>0)
stack2[k2]=i;
else if(v[i].position==2 && k==1)
stack2[++k2]=i;
}
out<<fixed;
for(register int i=1; i<=k; ++i)
out<<setprecision(6)<<v[stack1[i]].x<<" "<<setprecision(6)<<v[stack1[i]].y<<'\n';
for(register int i=k2; i>=1; --i)
out<<setprecision(6)<<v[stack2[i]].x<<" "<<setprecision(6)<<v[stack2[i]].y<<'\n';
return 0;
}