Pagini recente » Cod sursa (job #1932136) | Cod sursa (job #2530060) | Cod sursa (job #544896) | Cod sursa (job #2770757) | Cod sursa (job #2358541)
#include <bits/stdc++.h>
#define high 99999999
using namespace std;
struct Punct
{
double xp,yp;
};
int nrp;
double xc,yc;
double ymin,xmin;
int punctmin;
long long prod2;
Punct Puncte[120005];
Punct Stiva[120005];
int capstiva;
int i;
bool compareare(Punct,Punct);
long long prod(Punct,Punct,Punct);
int main()
{
cin>>nrp;
ymin=xmin=high;
for (i=1;i<=nrp;i++)
{
cin>>xc>>yc;
if (ymin>yc)
{
ymin=yc;
xmin=xc;
punctmin=i;
}
else if (ymin==yc&&xmin>xc)
{
xmin=xc;
punctmin=i;
}
Puncte[i].xp=xc;
Puncte[i].yp=yc;
}
swap(Puncte[1],Puncte[punctmin]);
punctmin=1;
sort(Puncte+2,Puncte+1+nrp,compareare);
for (i=1;i<=nrp;i++)
cout<<Puncte[i].xp<<" "<<Puncte[i].yp<<"\n";
capstiva++;
Stiva[capstiva]=Puncte[1];
for (i=2;i<=nrp;i++)
{
prod2=prod(Stiva[capstiva-1],Stiva[capstiva],Puncte[i]);
cout<<prod2<<"\n";
if (prod2==0)
Stiva[capstiva]=Puncte[i];
else if (prod2<0)
{
capstiva++;
Stiva[capstiva]=Puncte[i];
}
else
{
while (prod2>0)
{
capstiva--;
prod2=prod(Stiva[capstiva-1],Stiva[capstiva],Puncte[i]);
}
capstiva++;
Stiva[capstiva]=Puncte[i];
}
}
for (i=1;i<=capstiva;i++)
cout<<Stiva[i].xp<<" "<<Stiva[i].yp<<"\n";
return 0;
}
bool compareare(Punct X1,Punct X2)
{
long long prodcomp;
double dist1,dist2;
dist1=(X1.xp-Puncte[1].xp)*(X1.xp-Puncte[1].xp)+(X1.yp-Puncte[1].yp)*(X1.yp-Puncte[1].yp);
dist2=(X2.xp-Puncte[1].xp)*(X2.xp-Puncte[1].xp)+(X2.yp-Puncte[1].yp)*(X2.yp-Puncte[1].yp);
prodcomp=prod(Puncte[1],X1,X2);
if (prodcomp>0)
return 1;
else if (prodcomp==0&&dist1<dist2)
return 1;
return 0;
}
long long prod(Punct Origin,Punct X1,Punct X2)
{
return (X1.xp-Origin.xp)*(X2.yp-Origin.yp)-(X2.xp-Origin.xp)*(X1.yp-Origin.yp);
}