Pagini recente » Cod sursa (job #2347672) | Cod sursa (job #631675) | Cod sursa (job #2717937) | Cod sursa (job #360377) | Cod sursa (job #3222183)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
#define NMAX 1008
#define double long double
struct punct
{
double x,y;
bool operator == (punct const &a) const
{
return x==a.x && y==a.y;
}
};
punct p0;
int n,i,j;
vector<punct>v;
int orientation (punct a, punct b, punct c)
{
double v=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v<0)
{
return -1;///clockwise
}
if (v>0)
{
return 1; ///counter-clockwise
}
return 0;///collinear
}
bool cw (punct a, punct b, punct c, bool include_collinear)
{
int orientare=orientation(a,b,c);
return (orientare<0) || (include_collinear && orientare==0);
}
bool collinear (punct a, punct b, punct c)
{
return (orientation(a,b,c)==0);
}
bool crt (punct a, punct b)
{
int orientare=orientation(p0,a,b);
if (orientare==0)
{
if ((p0.x-a.x)*(p0.x-a.x)+(p0.y-a.y)*(p0.y-a.y)<(p0.x-b.x)*(p0.x-b.x)+(p0.y-b.y)*(p0.y-b.y))
{
return 1;
}
return 0;
}
return orientare<0;
}
void convex_hull (vector<punct>&a, bool include_collinear = true)
{
p0.y=100000005,p0.x=1000;
for (auto it : a)
{
if (it.y<p0.y)
{
p0=it;
}
if (it.y==p0.y)
{
if (it.x<p0.x)
{
p0=it;
}
}
}/// aflu punctul cel mai de jos
sort (a.begin(),a.end(),crt);
if (include_collinear)
{
int n=a.size()-1;
while (n>=0 && collinear(p0,a[n],a.back()))
{
n--;
}
reverse(a.begin()+n+1,a.end());
}
vector <punct>stiva;
for (auto it : a)
{
while (stiva.size()>1 && !cw(stiva[stiva.size()-2],stiva.back(),it,include_collinear))
{
stiva.pop_back();
}
stiva.push_back(it);
}
if (include_collinear==0 && stiva.size()==2 && stiva[0]==stiva[1])
{
stiva.pop_back();
}
a=stiva;
}
signed main()
{
fin>>n;
for (i=0; i<n; i++)
{
punct a;
fin>>a.x>>a.y;
v.push_back(a);
}
convex_hull(v);
reverse(v.begin()+1,v.end());
fout<<v.size()<<'\n';
for (auto it : v)
{
fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
}
return 0;
}