Pagini recente » Cod sursa (job #1603938) | Cod sursa (job #1740931) | Cod sursa (job #3260664) | Cod sursa (job #2331757) | Cod sursa (job #929331)
Cod sursa(job #929331)
#include <cstdio>
#include <deque>
#include <cmath>
#define mp make_pair
#define pb push_back
#define pf push_front
#define x first
#define y second
using namespace std;
const double prec=(pow(10,-12));
int n;
deque <pair<double,double> > ic; //inf convexa
inline double stanga(pair<double,double> p0, pair<double,double> p1, pair<double,double> p2)
{
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
double xx,yy;
pair<double,double> p[3];
for(int i=0;i<3;++i)
{
scanf("%lf%lf",&xx,&yy);
p[i]=mp(xx,yy);
}
if(stanga(p[0],p[1],p[2])>prec)
{
ic.pb(p[0]);
ic.pb(p[1]);
}
else
{
ic.pb(p[1]);
ic.pb(p[0]);
}
ic.pb(p[2]);
ic.pf(p[2]);
for(int i=3;i<n;++i)
{
scanf("%lf%lf",&xx,&yy);
p[0]=mp(xx,yy);
if(stanga(ic.back(),ic[ic.size()-2],p[0])>prec&&stanga(ic[1],ic.front(),p[0])>prec)
continue; // este in interiorul poligonului;
while(stanga(ic[ic.size()-2],ic.back(),p[0])<=prec)
ic.pop_back();
ic.pb(p[0]);
while(stanga(ic.front(),ic[1],p[0])<=prec)
ic.pop_front();
ic.pf(p[0]);
}
fclose(stdin);
freopen("infasuratoare.out","w",stdout);
for(int i=0;i<ic.size()-1;++i)
printf("%lf %lf\n",ic[i].x,ic[i].y);
fclose(stdout);
}
int main()
{
citire();
return 0;
}