Pagini recente » Rating Giurgea Alexandru (Giurgea_Alexandru) | Cod sursa (job #356004) | Cod sursa (job #1972675) | Cod sursa (job #154085) | Cod sursa (job #1802356)
#include <iostream>
#include <fstream>
#include <climits>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define NMax 120005
struct Point
{
double x, y;
} v[NMax],s[NMax];
int n,vf;
double cross_product(Point A, Point B, Point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
bool compare(Point x, Point y)
{
return cross_product(v[1],x,y) <0;
}
int main()
{
f>>n;
int poz=0;
v[poz].x=INT_MAX;
v[poz].y=INT_MAX;
for(int i=1;i<=n;++i)
{
f>>v[i].x>>v[i].y;
if(v[poz].x==v[i].x&&v[poz].y>v[i].y)
poz=i;
else if(v[poz].x>v[i].x) poz=i;
}
swap(v[poz],v[1]);
sort(v+2,v+n+1,compare);
vf=1;
s[vf]=v[1];
s[++vf]=v[2];
for(int i=3;i<=n;++i)
{
while(vf>=2&&(cross_product(s[vf-1],s[vf],v[i])>0))
--vf;
s[++vf]=v[i]; }
g<<vf<<'\n';
for(int i=vf;i>0;--i)
g<<fixed<<setprecision(6)<<s[i].x<<' '<<s[i].y<<'\n';
return 0;
}