Pagini recente » Cod sursa (job #42133) | Cod sursa (job #1867293) | Cod sursa (job #1929838) | Cod sursa (job #445241) | Cod sursa (job #719406)
Cod sursa(job #719406)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,d,st[120024];
struct point
{
long double x,y;
}p[120024];
long double isleft(point a,point b,point c)
{
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
bool comp(point a,point b)
{
long double k=isleft(p[1],a,b);
if(k>0) return 1;
return 0;
}
int main()
{
f>>n;
f>>p[1].x>>p[1].y;
for(i=2;i<=n;++i)
{
f>>p[i].x>>p[i].y;
if((p[i].x<p[1].x)||(p[i].x==p[1].x&&p[i].y<p[1].y))
{
point aux=p[1];
p[1]=p[i];
p[i]=aux;
}
}
sort(p+2,p+n+1,comp);
st[++d]=1;
for(i=2;i<=n;++i)
{
while(d>1&& isleft(p[st[d-1]],p[st[d]],p[i])<0) --d;
st[++d]=i;
}
g<<d<<"\n";
for(i=1;i<=d;++i) g<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
f.close();
g.close();
return 0;
}