Pagini recente » Cod sursa (job #1383266) | Cod sursa (job #1694525) | Cod sursa (job #2625366) | Cod sursa (job #2744547) | Cod sursa (job #1414050)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
using namespace std;
#define NMAX 120007
#define point pair < double , double >
#define x first
#define y second
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
point p[NMAX];
stack < point > inStack;
int i,N;
double cross(point A,point B,point C)
{
double a = A.y - B.y;
double b = B.x - A.x;
double c = A.x * B.y - B.x * A.y;
double product = a * C.x + b * C.y + c;
return product;
}
bool compare(point A,point B)
{
return ( cross(p[1],A,B) < 0);
}
void read()
{
f >> N;
for (i=1;i<=N;++i)
{
f >> p[i].x >> p[i].y;
if (p[i] < p[1]) swap(p[1],p[i]);
}
sort(p+2,p+N+1,compare);
}
void convexHull()
{
inStack.push(p[1]);
inStack.push(p[2]);
for (i=3;i<=N;++i)
{
while (inStack.size() >= 2)
{
point prv = inStack.top();
inStack.pop();
point prvv = inStack.top();
if (cross(prvv , prv , p[i]) > 0) continue;
else
{
inStack.push(prv);
break;
}
}
inStack.push(p[i]);
}
}
void writeConvexHull()
{
g << inStack.size() << '\n';
while (inStack.size())
{
g << fixed << setprecision(13);
g << inStack.top().first << " ";
g << fixed << setprecision(13);
g << inStack.top().second << '\n';
inStack.pop();
}
}
int main()
{
read();
convexHull();
writeConvexHull();
return 0;
}