Pagini recente » Cod sursa (job #1428753) | Cod sursa (job #2565886) | Cod sursa (job #984109) | Cod sursa (job #404386) | Cod sursa (job #1141909)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>
#define M -2000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y,tg;
};
punct L[120001];
struct coord{double xx,yy;};
double minx=-M,miny=-M;int n;
int sf;
int sgn(double x){if(x<1)return -1;if(x>1)return 1;return 0;}
vector<coord>sol;
void muta(double &x,double &y)
{
x=x-minx;
y=y-miny;
}
int cmp(punct a,punct b)
{
return a.tg>b.tg;
}
void citire()
{
int i;
f>>n;
for(i=1;i<=n;i++)
{
f>>L[i].x>>L[i].y;
if(minx>L[i].x)
{
minx=L[i].x;
miny=L[i].y;
}
else
if(minx==L[i].x)
if(miny>L[i].y)
miny=L[i].y;
}
for(i=1;i<=n;i++) muta(L[i].x,L[i].y);
for(i=1;i<=n;i++) L[i].tg=atan2(L[i].y,L[i].x);
}
double determinant(coord a,coord b,coord c)
{
double nr=(a.xx*b.yy)+(b.xx*c.yy)+(a.yy*c.xx)-(b.yy*c.xx)-(a.yy*b.xx)-(a.xx*c.yy);
return nr;
}
void afisare()
{
g<<sf<<'\n';
int i;
minx=-minx;
miny=-miny;
for(i=0;i<sf;i++)
muta(sol[i].xx,sol[i].yy);
for(i=sf-1;i>=0;i--)
g<<fixed<<setprecision(6)<<sol[i].xx<<" "<<sol[i].yy<<'\n';
}
void infasuratoare()
{
int i;
coord c;
c.xx=0;c.yy=0;sol.push_back(c);
c.xx=L[1].x;c.yy=L[1].y;sol.push_back(c);
// c.xx=L[2].x;c.yy=L[2].y;sol.push_back(c);
sf=2;
for(i=2;i<=n;i++)
{
c.xx=L[i].x;c.yy=L[i].y;
while(sol.size()>=2&&determinant(sol[sf-2],c,sol[sf-1])<0)
{
sol.pop_back();
sf--;
}
sol.push_back(c);sf++;
}
}
int main()
{ int i;
citire();
sort(L+1,L+n+1,cmp);
infasuratoare();
afisare();
/* for(i=1;i<=n;i++)
g<<L[i].x<<" "<<L[i].y<<" "<<L[i].tg<<'\n';*/
return 0;
}