Pagini recente » Cod sursa (job #177240) | Cod sursa (job #945684) | Cod sursa (job #1347810) | Cod sursa (job #2477771) | Cod sursa (job #1141505)
#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-sgn(minx)*abs((double)minx);
y=y-sgn(miny)*abs((double)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].x,L[i].y);
}
double determinant(coord a,coord b,coord c)
{
double nr=(a.xx-c.xx)*(b.yy-c.yy)-(a.yy-c.yy)*(b.xx-c.xx);
return sgn(nr);
}
void afisare()
{
g<<sf<<'\n';
int i;
minx=-minx;
miny=-miny;
for(i=0;i<sol.size();i++)
muta(sol[i].xx,sol[i].yy);
for(i=sol.size()-1;i>=1;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=3;i<=n;i++)
{
coord c;c.xx=L[i].x;c.yy=L[i].y;
while(sf>=2&&determinant(sol[sf-1],sol[sf],c)>0)sf--;
sol.push_back(c);sf++;
}
afisare();
}
int main()
{ int i;
citire();
sort(L+1,L+n+1,cmp);
infasuratoare();
/* for(i=1;i<=n;i++)
g<<L[i].x<<" "<<L[i].y<<" "<<L[i].tg<<'\n';*/
return 0;
}