Pagini recente » Cod sursa (job #3263398) | Cod sursa (job #738685) | Cod sursa (job #340255) | Cod sursa (job #165537) | Cod sursa (job #1645135)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,st[120001],vf,poz;
struct punct
{
double x,y;
}p1,p2,p3,v[120001];
double intoarcere(punct a,punct b,punct c)
{
double x=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
return x;
}
bool compare(punct a,punct b)
{
return intoarcere(v[1],a,b)<0;
}
int main()
{
ifstream f("infasuratoare.in");f>>n;
for(i=1;i<=n;i++){f>>v[i].x>>v[i].y;}//cout<<v[i].x<<" "<<v[i].y<<'\n';}
f.close();poz=1;
for(i=2;i<=n;i++)
{
if(v[i].x==v[poz].x&&v[i].y<v[poz].y)poz=i;
else if(v[i].x<v[poz].x)poz=i;
}
p1=v[poz];v[poz]=v[1];v[1]=p1;
sort(v+2,v+1+n,compare);//for(i=1;i<=n;i++)cout<<v[i].x<<" "<<v[i].y<<'\n';
st[1]=1;st[2]=2;vf=2;
for(i=3;i<=n;i++)
{
while(vf>1&&intoarcere(v[st[vf-1]],v[st[vf]],v[i])>0)vf--;
vf++;st[vf]=i;
}
ofstream g("infasuratoare.out");g<<vf<<'\n';
for(i=vf;i>0;i--)
{
n=st[i];
g<<v[n].x<<" "<<v[n].y<<'\n';
}
g.close();
return 0;
}