Pagini recente » Cod sursa (job #801618) | Cod sursa (job #1675935) | Cod sursa (job #286865) | Cod sursa (job #2122220) | Cod sursa (job #1668602)
#include<bits/stdc++.h>
#define N 125000
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point{
double x;
double y;
};
point p[N],s[N];
int n,k;
double asdf(const point &p1,const point &p2,const point &p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
bool compare(const point &p1, const point &p2)
{
return asdf(p[1],p1,p2);
}
int main()
{
int i,j=1;
in>>n;
for (i=1;i<=n;i++) {
in>>p[i].x>>p[i].y;
if( p[i].y<p[j].y || (p[i].y==p[j].y && p[i].x<p[j].x))
j=i;
}
swap(p[1],p[j]);
sort(p+2,p+n+1,compare);
s[++k]=p[1];
s[++k]=p[2];
for (i=3;i<=n;i++) {
while( k>=2 && asdf(s[k-1],s[k],p[i])<0 )
k--;
s[++k]=p[i];
}
out<<k<<'\n';
for(i=1;i<=k;i++) {
out<<setprecision(6)<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
}
return 0;
}