Pagini recente » Cod sursa (job #1419490) | Cod sursa (job #90951) | Cod sursa (job #502623) | Cod sursa (job #225623) | Cod sursa (job #690107)
Cod sursa(job #690107)
#include <cstdio>
#include <algorithm>
#define inf 1000000000
#define nMax 120010
using namespace std;
struct ceva{
double x;
double y;
long double panta;
}a[nMax],stiva[nMax];
int n;
int nrPc;
int Xmin,Ymin;
bool cmp(ceva i,ceva j)
{
return (i.panta<j.panta);
}
void read()
{
Xmin=Ymin=1000000010;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if (Xmin>a[i].x)
{
Xmin=a[i].x;
Ymin=a[i].y;
}
else
if (Xmin==a[i].x)
if(Ymin>a[i].y){
Xmin=a[i].x;
Ymin=a[i].y;
}
}
}
long double Panta(ceva i,ceva j)
{
if (i.x==j.x)
return inf;
else
return ((i.y-j.y)/(i.x-j.x));
}
void solve_panta()
{
ceva aux;
aux.x=Xmin;
aux.y=Ymin;
for (int i=1;i<=n;i++){
if (!(a[i].x==Xmin && a[i].y==Ymin))
a[i].panta=Panta(aux,a[i]);
else
if (a[i].x==Xmin && a[i].y==Ymin)
a[i].panta=-inf;
}
}
long double determinant(ceva A,ceva B,ceva C)
{
return (A.x*B.y + A.y*C.x + B.x*C.y - B.y*C.x - C.y*A.x - A.y*B.x);
}
void solve()
{
nrPc=0;
stiva[++nrPc]=a[1];
stiva[++nrPc]=a[2];
for (int i=3;i<=n;i++)
{
if (determinant(stiva[nrPc-1],stiva[nrPc],a[i])>=0)
stiva[++nrPc]=a[i];
else{
while (determinant(stiva[nrPc-1],stiva[nrPc],a[i])<0)
nrPc--;
//nrPc++;
i--;
}
}
}
void print()
{
printf("%d\n",nrPc);
for (int i=1;i<=nrPc;i++)
printf("%0.6lf %0.6lf\n",stiva[i].x,stiva[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
solve_panta();
sort(a+1,a+n+1,cmp);
solve();
print();
return 0;
}