Pagini recente » Cod sursa (job #1543564) | Cod sursa (job #2953092) | Cod sursa (job #2562990) | Cod sursa (job #2542764) | Cod sursa (job #1135933)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct point
{
double x,y;
}p[120000];
int n,s[120000],si;
double area(point p1,point p2,point p3)
{
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}
bool cmp(point p1,point p2)
{
return area(*p,p1,p2)>0;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main()
{
int i;
fin>>n;
for(i=0;i<n;++i)
{
fin>>p[i].x>>p[i].y;
if(p[i].x<p[0].x)
swap(p[0],p[i]);
}
sort(p+1,p+n,cmp);
for(i=1;i<n;++i)
{
while(si)
if(area(p[s[si-1]],p[s[si]],p[i])>0)
break;
else
--si;
s[++si]=i;
}
fout<<++si<<"\n"<<setprecision(12)<<fixed;
for(i=0;i<si;++i)
fout<<p[s[i]].x<<" "<<p[s[i]].y<<"\n";
return 0;
}