Pagini recente » Cod sursa (job #201673) | Istoria paginii utilizator/byacnas | Atasamentele paginii eusebiu_oji_2017_cls11-12 | Rating Gorea Rares-Andrei (raresgorea) | Cod sursa (job #1042045)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
typedef pair <double,double> punct;
#define x first
#define y second
const int MAXN=120005;
int n;
punct v[MAXN];
punct stack[MAXN];
int head;
void citire()
{
f>>n;
for (int i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
}
inline double produs_vect (const punct &A, const punct &B, const punct &C)
{
return (B.x-A.x) * (C.y-A.y) - (B.y-A.y) * (C.x-A.x);
}
inline int cmp (const punct &p1, const punct &p2)
{
return produs_vect(v[1],p1,p2)<0;
}
void sortare ()
{
int pos=1;
for (int i=2;i<=n;i++)
if (v[i]<v[pos])
pos=i;
swap(v[i],v[pos]);
sort(v+2,v+n+1,cmp);
}
void infasuratoare()
{
sortare();
stack[1]=v[1];
stack[2]=v[2];
head=2;
for (int i=3;i<=n;i++)
{
while(head>=2 && produs_vect(stack[head-1],stack[head],v[i])>0)
--head;
stack[++head]=v[i];
}
}
void afisare()
{
g<<fixed;
g<<head<<"\n";
for (int i=head;i>=1;--i)
g<<setprecision(9)<<stack[i].x<<" "<<stack[i].y<<"\n";
}
int main()
{
citire();
infasuratoare();
afisare();
return 0;
}