Pagini recente » Cod sursa (job #2756908) | Cod sursa (job #2765164) | Cod sursa (job #1382186) | Cod sursa (job #1522671) | Cod sursa (job #661229)
Cod sursa(job #661229)
#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 double panta(Punct A,Punct B,Punct C)
{
int a,b,c;
dreapta(A,C,a,b,c);
return a * B.x - b*B.y + c;
}
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++)
{
while (m>1 && panta(a[i],v[m],v[m-1])<0)
m--;
v[++m]=a[i];
}
for (i=n-1;i>1;i--)
{
while (m>1 && panta(a[i],v[m],v[m-1])>0)
m--;
v[++m]=a[i];
}
out<<m<<"\n";
for (int i=1;i<=m;i++)
out<<v[i].x<<" "<<v[i].y<<"\n";
return 0;
}