Pagini recente » Cod sursa (job #2069227) | Cod sursa (job #1125230) | Cod sursa (job #2913383) | Cod sursa (job #1267219) | Cod sursa (job #1645072)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,st[120001],vf;
struct punct
{
double x,y;
}p1,p2,p3,v[120001];
bool compare(punct a,punct b)
{
if(a.y==b.y)return(a.x<b.x);
return(a.y<b.y);
}
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;
}
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();
sort(v+1,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=1;i<=vf;i++)
{
n=st[i];
g<<v[n].x<<" "<<v[n].y<<'\n';
}
g.close();
return 0;
}