Pagini recente » Cod sursa (job #3335986) | Cod sursa (job #2053430) | Cod sursa (job #1964672) | Cod sursa (job #3339170) | Cod sursa (job #3355717)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct q
{
double x, y;
};
q v[120005], st[240005];
bool cmp(q a, q b)
{
if(a.x<b.x)
{
return true;
}
else if(a.x>b.x)
{
return false;
}
else
{
if(a.y<b.y)
{
return true;
}
return false;
}
}
double arie(q a, q b, q c)
{
return 0.5*((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
int k=0;
for(int i=1;i<=n;i++)
{
while(k>=2 && arie(st[k-1], st[k], v[i])<=0)
{
k--;
}
st[++k]=v[i];
}
int t=k;
for(int i=n-1;i>=1;i--)
{
while(k>t && arie(st[k-1], st[k], v[i])<=0)
{
k--;
}
st[++k]=v[i];
}
k--;
fout<<k<<"\n";
for(int i=1;i<=k;i++)
{
fout<<st[i].x<<" "<<st[i].y<<"\n";
}
return 0;
}