Pagini recente » Cod sursa (job #1668180) | Cod sursa (job #1260587) | Cod sursa (job #689643) | Cod sursa (job #1627633) | Cod sursa (job #896847)
Cod sursa(job #896847)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef struct{double x,y;}PUNCT;
PUNCT pct[120001];
int st[120001];
void schimba(PUNCT &a, PUNCT &b)
{
PUNCT aux;
aux=a;
a=b;
b=aux;
}
double crprod(PUNCT a,PUNCT b,PUNCT c)
{
return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
bool comp(PUNCT a, PUNCT b)
{
if(crprod(pct[1],a,b)<0)
return 1;
return 0;
}
int main()
{
int n,i,lst;
ifstream f("infasuratoare.in");
f>>n;
for(i=1;i<=n;i++)
f>>pct[i].x>>pct[i].y;
f.close();
for(i=2;i<=n;i++)
{
if(pct[i].x<pct[1].x)
schimba(pct[i],pct[1]);
else
if((pct[i].x==pct[1].x)&&(pct[i].y<pct[1].y))
schimba(pct[i],pct[1]);
}
sort(pct+2,pct+1+n,comp);
st[1]=1;
st[2]=2;
lst=2;
for(i=3;i<=n;i++)
{
while((lst>=2)&&(crprod(pct[st[lst-1]],pct[st[lst]],pct[i])>=0))
lst--;
lst++;
st[lst]=i;
}
while((lst>=2)&&(crprod(pct[st[lst-1]],pct[st[lst]],pct[1])>=0))
lst--;
ofstream g("infasuratoare.out");
g<<fixed;
g<<lst<<'\n';
for(i=lst;i>0;i--)
g<<setprecision(12)<<pct[st[i]].x<<" "<<pct[st[i]].y<<"\n";
g.close();
return 0;
}