Pagini recente » Cod sursa (job #2838173) | Cod sursa (job #433604) | Borderou de evaluare (job #156614) | Cod sursa (job #1649935) | Cod sursa (job #3269975)
#include<fstream>
#include<algorithm>
#include<vector>
#define INF 999999999
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
struct point{
double x, y;
};
int n;
std::vector<point>v;
inline double det(point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(const point &a, const point &b){
point aux={0, 0};
double d=det(aux, a, b);
return (d>0);
};
int main()
{
point s[120005];
int k=0, pmin;
fin>>n;
v=std::vector<point>(n+5);
v[0]={INF, INF};
for(int i=1; i<=n; ++i)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<v[pmin].y || (v[i].y==v[pmin].y && v[i].x<v[pmin].x))
pmin=i;
}
v[0]=v[pmin];
v[pmin]=v[1];
v[1]=v[pmin];
for(int i=1; i<=n; ++i)
{
v[i].x-=v[0].x;
v[i].y-=v[0].y;
}
std::sort(v.begin()+2, v.begin()+n+1, cmp);
s[1]=v[1];
s[2]=v[2];
k=2;
for(int i=3; i<=n; ++i)
{
while(k>=2 && det(s[k-1], s[k], v[i])<0)
--k;
s[++k]=v[i];
}
fout<<k<<'\n';
for(int i=1; i<=k; ++i)
fout<<s[i].x+v[0].x<<' '<<s[i].y+v[0].y<<'\n';
return 0;
}