Pagini recente » Cod sursa (job #1525250) | Cod sursa (job #2834209) | Cod sursa (job #1968806) | Cod sursa (job #259083) | Cod sursa (job #2878691)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct puncte
{
double x, y;
} punct[120001], stiva_dr[120001], stiva_st[120001], stanga[120001], dreapta[120001];
double arie(double x1, double y1, double x2, double y2, double x3, double y3)
{
return (x1*y2+x2*y3+x3*y1-y3*x1-y2*x3-x2*y1)/2.0;
}
double comparare(puncte a, puncte b)
{
if (a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
int main()
{
int n;
fin >> n;
for (int i=1; i<=n; i++)
fin >> punct[i].x >> punct[i].y;
sort(punct + 1, punct + n + 1, comparare);
int contor_dr=0, contor_st=0, k=0, l=0;
for(int i=1; i<=n; i++)
if(arie(punct[1].x, punct[1].y, punct[n].x, punct[n].y, punct[i].x, punct[i].y)>0)
dreapta[++contor_dr]=punct[i];
else
stanga[++contor_st]=punct[i];
/*
cout << '\n';
for(int i=1; i<=contor_st; i++)
cout << stanga[i].x <<' '<<stanga[i].y<<'\n';
*/
stiva_dr[++k]=punct[1];
stiva_dr[++k]=dreapta[1];
for(int i=2; i<=contor_dr; i++)
{
while(arie(stiva_dr[k-1].x, stiva_dr[k-1].y, stiva_dr[k].x, stiva_dr[k].y, dreapta[i].x, dreapta[i].y)>0 && k>=2)
k--;
stiva_dr[++k]=dreapta[i];
}
/*
cout << '\n';
for(int i=1; i<=k; i++)
cout << stiva_dr[i].x <<' '<< stiva_dr[i].y <<'\n';
*/
stiva_st[++l]=punct[1];
stiva_st[++l]=stanga[1];
for(int i=2; i<=contor_st; i++)
{
while(arie(stiva_st[l-1].x, stiva_st[l-1].y, stiva_st[l].x, stiva_st[l].y, stanga[i].x, stanga[i].y)<0 && l>=2)
l--;
stiva_st[++l]=stanga[i];
}
/*
cout << '\n';
for(int i=1; i<=l; i++)
cout << stiva_st[i].x <<' '<< stiva_st[i].y <<'\n';
*/
fout << k+l-2 <<'\n';
for(int i=2; i<=l; i++)
fout <<fixed<<setprecision(12)<< stiva_st[i].x <<' '<< stiva_st[i].y <<'\n';
//fout << punct[n].x <<' '<< punct[n].y <<'\n';
for(int i=k; i>1; i--)
fout << stiva_dr[i].x <<' '<<stiva_dr[i].y <<'\n';
}