Pagini recente » Cod sursa (job #404518) | Cod sursa (job #482643) | Cod sursa (job #2842617) | Cod sursa (job #2007684) | Cod sursa (job #1776567)
#include <cmath>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define as a.size()
#define hs h.size()
using namespace std;
struct point {
double x,y,a;
} mp;
vector <point> a,h;
void lire()
{
ifstream f("infasuratoare.in");
int n; point p;
f >> n >> mp.x >> mp.y;
a.push_back(mp);
for (int i=1; i<n ; i++)
{
f >> p.x >> p.y;
if (p.x<mp.x || p.x==mp.x && p.y<mp.y) mp=p;
a.push_back(p);
}
}
void ca()
{
double x,y;
for (int i=0; i<as; i++)
{
x=a[i].x-mp.x;
y=a[i].y-mp.y;
if (x==0 && y==0) a[i].a=1.1;
else a[i].a=y*abs(y)/(x*x+y*y);
}
}
double det(point a,point b, point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool cA(point a, point b)
{
if (a.a<b.a) return true; else return false;
}
void hull()
{
for (int i=0; i<4; i++)
{
h.push_back(a[i]);
}
if (det(h[0],h[1],h[2])<=0)
{
h[1]=h[2];
h.pop_back();
}
for (int i=3; i<as; i++)
{
h.push_back(a[i]);
while (hs>2 && det(h[hs-3],h[hs-2],h[hs-1])<=0)
{
h[hs-2]=h[hs-1];
h.pop_back();
}
}
}
void ecrire()
{
ofstream f("infasuratoare.out");
f << fixed;
f << hs << '\n';
for (int i=0; i<hs; i++)
{
f << setprecision(9) << h[i].x << ' ' << h[i].y << '\n';
}
}
main()
{
lire();
ca();
sort(a.begin(),a.end(),cA);
hull();
ecrire();
}