Pagini recente » Cod sursa (job #2749999) | Cod sursa (job #3200007) | Cod sursa (job #1154478) | Cod sursa (job #905939) | Cod sursa (job #3214388)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define PAIR pair <double,double>
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,k,i;
PAIR V[120002],st[120002],aux;
int cadran(const PAIR &a)
{
double x=a.first;
double y=a.second;
if(x>0&&y>=0)
return 1;
if(x>=0&&y<0)
return 4;
if(x<=0&&y>0)
return 2;
return 3;
}
double det(const PAIR &a,const PAIR &b,const PAIR &c)
{
return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
bool cmp(const PAIR &a,const PAIR &b)
{
int c1=cadran(a);
int c2=cadran(b);
if(c1!=c2)
return c1<c2;
double d=det(V[1],a,b);
if(d!=0)
return d>0;
else
return a.first*a.first+a.second*a.second<b.first*b.first+b.second*b.second;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
fin>>V[i].first>>V[i].second;
poz=1;
for(i=2;i<=n;i++)
if(V[i]<V[poz])
poz=i;
swap(V[poz],V[1]);
sort(V+2,V+n+1,cmp);
st[1]=V[1];
st[2]=V[2];
k=2;
for(i=3;i<=n;i++)
{
while(k>=2&&det(st[k-1],st[k],V[i])<=0)
k--;
st[++k]=V[i];
}
fout<<k<<"\n";
for(i=1;i<=k;i++)
fout<<setprecision(9)<<fixed<<st[i].first<<" "<<st[i].second<<"\n";
return 0;
}