Pagini recente » Cod sursa (job #305836) | Cod sursa (job #102846) | Cod sursa (job #2414489) | Cod sursa (job #282698) | Cod sursa (job #3030314)
#include <fstream>
#include <algorithm>
#include <iomanip>
const int NMAX=120005;
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
ld det(ld, ld, ld, ld, ld, ld);
void infasuratoare();
struct punct
{
ld x, y;
bool operator<(const punct& other) const
{
if(det(0, 0, x, y, other.x, other.y)==0) return x<other.x;
return (det(0, 0, x, y, other.x, other.y)<0);
}
}v[NMAX], s[NMAX];
int n;
int main()
{
int i;
fin>>n;
for(i=1; i<=n; i++) fin>>v[i].x>>v[i].y;
infasuratoare();
return 0;
}
void infasuratoare()
{
int i, cnt=0;
sort(v+1, v+n+1);
s[++cnt]=v[1];
s[++cnt]=v[2];
for(i=3; i<=n; i++)
{
while(cnt>=2 && det(v[i].x, v[i].y, s[cnt-1].x, s[cnt-1].y, s[cnt].x, s[cnt].y)>0)
{
cnt--;
}
s[++cnt]=v[i];
}
fout<<cnt<<'\n';
for(i=cnt; i>=1; i--) fout<<fixed<<setprecision(10)<<s[i].x<<' '<<s[i].y<<'\n';
}
ld det(ld x3, ld y3, ld x1, ld y1, ld x2, ld y2)
{
return x1*(y2-y3)-y1*(x2-x3)+(x2*y3-y2*x3);
}