Pagini recente » Cod sursa (job #169405) | Cod sursa (job #1637154) | Cod sursa (job #2671620) | Cod sursa (job #1874909) | Cod sursa (job #2551927)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
long double x,y;
};
ura coord[120010],st1[120010],st2[120010];
bool cmp(ura a,ura b)
{
if (a.y>b.y)
return true;
else
if (a.y<b.y)
return false;
else
if (a.x>b.x)
return true;
else
return false;
}
int pozitie(ura p3,ura p1,ura p2)
{
long double a,b,c,s;
a=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y;
b=p3.x*p2.y+p1.x*p3.y+p2.x*p1.y;
c=a-b;
s=1.0*1/2*c;
if (s<0)///punctul e la dreapta
return 1;
else
if (s>0)///punctul e la stanga
return -1;
return 0;
}
int main()
{
int n,i,k1,k2;
cin>>n;
for (i=1; i<=n; i++)
cin>>coord[i].x>>coord[i].y;
sort (coord+1,coord+n+1,cmp);
k1=0;
st1[0]=coord[1];
for (i=2; i<n; i++)
if (pozitie(coord[i],coord[1],coord[n])==1)
{
while (pozitie(coord[i],st1[k1],st1[k1-1])==-1 && k1!=0)
k1--;
k1++;
st1[k1]=coord[i];
}
while (pozitie(st1[k1],st1[k1-1],coord[n])==-1 && k1>=2)
k1--;
k2=0;
st2[0]=coord[n];
for (i=n-1; i>=2; i--)
if (pozitie(coord[i],coord[1],coord[n])==-1)
{
while (pozitie(coord[i],st2[k2],st2[k2-1])==-1 && k2!=0)
k2--;
k2++;
st2[k2]=coord[i];
}
while (pozitie(st2[k1],st2[k1-1],coord[1])==-1 && k2>=2)
k2--;
cout<<2+k1+k2<<"\n";
cout<<fixed<<setprecision(12)<<coord[n].x<<" "<<fixed<<setprecision(12)<<coord[n].y<<"\n";
for (i=1; i<=k2; i++)
cout<<fixed<<setprecision(12)<<st2[i].x<<" "<<fixed<<setprecision(12)<<st2[i].y<<"\n";
cout<<fixed<<setprecision(12)<<coord[1].x<<" "<<fixed<<setprecision(12)<<coord[1].y<<"\n";
for (i=1; i<=k1; i++)
cout<<fixed<<setprecision(12)<<st1[i].x<<" "<<fixed<<setprecision(12)<<st1[i].y<<"\n";
return 0;
}