Pagini recente » Cod sursa (job #1157438) | Cod sursa (job #2351632) | Cod sursa (job #1267790) | Cod sursa (job #2958248) | Cod sursa (job #661595)
Cod sursa(job #661595)
#include <fstream>
#include <algorithm>
using namespace std;
const int N=120005;
struct Punct
{
double x,y;
} v[2*N],a[N];
int n,m;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
inline bool cmp(const Punct &a,const Punct &b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
inline bool panta(Punct A,Punct B,Punct C)
{
return (B.y - A.y) * (C.x - A.x) > (B.x - A.x) * (C.y - A.y);
}
void del(Punct X)
{
while (m>1 && panta(v[m-1],v[m],X))
m--;
}
int main()
{
int i;
in>>n;
for (i=1;i<=n;i++)
in>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++)
{
del(a[i]);
v[++m]=a[i];
}
for (i=n-1;i>1;i--)
{
del(a[i]);
v[++m]=a[i];
}
del(a[1]);
out<<m<<"\n";
for (int i=1;i<=m;i++)
out<<v[i].x<<" "<<v[i].y<<"\n";
return 0;
}