Pagini recente » Cod sursa (job #934925) | Cod sursa (job #1104321) | Cod sursa (job #1778626) | Cod sursa (job #2774777) | Cod sursa (job #661586)
Cod sursa(job #661586)
#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 void dreapta(Punct A,Punct B,int &a,int &b,int &c)
{
a = A.y - B.y;
b = A.x - B.x;
c = A.x * B.y - B.x * A.y;
}
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,L;
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;
}