Pagini recente » Cod sursa (job #967441) | Cod sursa (job #3216250) | Cod sursa (job #2417823) | Cod sursa (job #41392) | Cod sursa (job #2857398)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#define zero 1e-12
#define N 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
double x, y;
} a[N];
int n;
bitset <N> viz;
void citire()
{
fin>>n;
for (int i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
fin.close();
}
inline bool cmp(punct a, punct b)
{
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
double aria(punct o, punct a, punct b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
void convex_hull()
{
///sortam elementele dupa x si dupa y
sort(a+1, a+n+1, cmp);
int st[N];
int top; ///stiva
///adaugam in stiva prima muchie intre pct 1 si 2
st[1]=1; st[2]=2; top=2;
viz[2]=1;
for (int i=1, p=1; i>0; i+=(p=(i==n ? -p:p)))
if (!viz[i])
{
while (top>=2 && aria(a[st[top-1]], a[st[top]], a[i])<zero)
viz[st[top--]]=0;
st[++top]=i;
viz[i]=1;
}
fout<<top-1<<'\n';
fout<<setprecision(6)<<fixed;
for (int i=1; i<top; ++i)
fout<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
}
int main()
{
citire();
convex_hull();
return 0;
}