Pagini recente » Cod sursa (job #1868871) | Cod sursa (job #2495807) | Cod sursa (job #2960431) | Cod sursa (job #2295844) | Cod sursa (job #2134333)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j;
struct punct{double x,y;}a[120001],st[120001];
double det(punct A,punct B,punct C){
return A.x*B.y-A.y*B.x+B.x*C.y-B.y*C.x+C.x*A.y-C.y*A.x;
}
bool cmp(punct A,punct B){
if(det(a[1],A,B)>0)
return 1;
else
return 0;
}
int main()
{
f>>n;
j=1;
for(i=1 ; i<=n ; ++i)
{
f>>a[i].x>>a[i].y;
if(a[i].x<a[j].x || (a[i].x==a[j].x && a[i].y<a[j].y))
j=i;
}
swap(a[1],a[j]);
sort(a+2,a+n+1,cmp);
st[1]=a[1];
st[2]=a[2];
j=2;
for(i=3 ; i<=n ; ++i)
{
while(j>=2 && det(st[j-1],st[j],a[i])<0)
j--;
st[++j]=a[i];
}
g<<j<<'\n';
for(i=1 ; i<=j ; ++i)
g<<fixed<<setprecision(6)<<st[i].x<<" "<<fixed<<setprecision(6)<<st[i].y<<'\n';
return 0;
}