Pagini recente » Cod sursa (job #2054639) | Cod sursa (job #1168757) | Cod sursa (job #1336197) | Cod sursa (job #1755652) | Cod sursa (job #1679064)
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct puncte{
double x,y;
double cosinus;
}x[120001],minim;
puncte stiva[1000];
puncte p1;
void adaugare(int &n,puncte inf[],puncte v){
//n++;
inf[n]=v;
int k=n;
puncte aux;
while(k!=1)
if(inf[k].cosinus<inf[k/2].cosinus||(inf[k].cosinus==inf[k/2].cosinus&&sqrt((inf[k].x-minim.x)*(inf[k].x-minim.x)-(inf[k].y-minim.y)*(inf[k].y-minim.y))>sqrt((inf[k/2].x-minim.x)*(inf[k/2].x-minim.x)-(inf[k/2].y-minim.y)*(inf[k/2].y-minim.y))))
{aux=inf[k];
inf[k]=inf[k/2];
inf[k/2]=aux;
k/=2;}
else
k=1;}
void eliminare(int &n,puncte inf[],puncte &v){
v=inf[1];
inf[1]=inf[n];
n--;
int k=1;
while(2*k<=n)
{int vmax;
puncte aux;
if(2*k+1<=n)
if(inf[2*k].cosinus<inf[2*k+1].cosinus)
vmax=2*k;
else
vmax=2*k+1;
else
vmax=2*k;
if(inf[vmax].cosinus<inf[k].cosinus)
{aux=inf[vmax];
inf[vmax]=inf[k];
inf[k]=aux;
k=vmax;}
else
k=n+1;}}
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
fin>>x[i].x>>x[i].y;
minim.y=x[1].y;
minim.x=x[1].x;
for(int i=1;i<=n;i++)
{if(x[i].y<minim.y)
{minim.y=x[i].y;
minim.x=x[i].x;}
if(x[i].y==minim.y)
if(x[i].x<minim.x)
minim.x=x[i].x;}
//fout<<minim.x<<" "<<minim.y<<" ";
//fout<<"\n";
for(int i=1;i<=n;i++)
if(x[i].x==minim.x&&x[i].y==minim.y)
x[i].cosinus=2;
else
{double ip=sqrt((minim.x-x[i].x)*(minim.x-x[i].x)+(minim.y-x[i].y)*(minim.y-x[i].y));
double cal=x[i].x-minim.x;
x[i].cosinus=cal/ip;}
//for(int i=1;i<=n;i++)
//fout<<x[i].cosinus<<"\n";
for(int i=1;i<=n;i++)
adaugare(i,x,x[i]);
int k=n;
while(k!=1)
{puncte v;
eliminare(k,x,v);
x[k+1]=v;}
//fout<<"\n";
//for(int i=1;i<=n;i++)
// fout<<x[i].x<<" "<<x[i].y<<"\n";//<<x[i].cosinus<<"\n";
for(int i=1;i<=3;i++)
stiva[i]=x[i];
int p=3;
for(int i=4;i<=n;i++)
{
double d=stiva[p-1].x*stiva[p].y+stiva[p].x*x[i].y+x[i].x*stiva[p-1].y-
x[i].x*stiva[p].y-stiva[p-1].x*x[i].y-stiva[p].x*stiva[p-1].y;
if(d<=0)
stiva[p]=x[i];
else
p++,stiva[p]=x[i];
}
fout<<p<<"\n";
for(int i=1;i<=p;i++)
fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
fout<<"\n";
/*double arietotala=0;
for(int i=3;i<=p;i++)
{//fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
//fout<<stiva[i-1].x<<" "<<stiva[i-1].y<<"\n\n";
double d=abs(double(stiva[1].x*stiva[i].y+stiva[1].y*stiva[i-1].x+stiva[i].x*stiva[i-1].y
-stiva[i].y*stiva[i-1].x-stiva[i-1].y*stiva[1].x-stiva[1].y*stiva[i].x));
double arie=1/2.0*d;
fout<<arie<<"\n";
arietotala+=arie;}
fout<<arietotala;*/
return 0;
}