Pagini recente » Cod sursa (job #3275201) | Cod sursa (job #2943104) | Cod sursa (job #1121086) | Cod sursa (job #440801) | Cod sursa (job #1142615)
#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
{
long double x,y,tg;
};
punct L[120001];
struct coord{long double xx,yy;};
long double minx=-M,miny=-M;int n;
int sf;
vector<coord>sol;
void muta(long double &x,long 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);
}
long double determinant(coord a,coord b,coord c)
{
long double nr=(a.xx-c.xx)*(b.yy-c.yy)-(a.yy-c.yy)*(b.xx-c.xx);
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(12)<<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;
}