Pagini recente » Cod sursa (job #1150349) | Cod sursa (job #19415) | Cod sursa (job #570887) | Cod sursa (job #2782596) | Cod sursa (job #1359022)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream F("infasuratoare.in");
ofstream G("infasuratoare.out");
const int N = 120010;
struct pt {
double x,y;
};
pt make_point(double x,double y)
{
pt p;
p.x = x;
p.y = y;
return p;
}
bool cmp(pt x,pt y)
{
return x.x < y.x || ( x.x == y.x && x.y < y.y );
}
int ecu(pt p1,pt p2,pt p3)
{
double a = p1.y - p2.y;
double b = p2.x - p1.x;
double c = - p1.y * p2.x + p1.x * p2.y;
return ( a*p3.x + b*p3.y + c > 0 );
}
int n;
vector<pt> points,hull,stack;
void add(pt x)
{
if ( stack.size() >= 2 )
while ( !ecu(stack[stack.size()-2],x,stack.back()) )
{
stack.pop_back();
if ( stack.size() < 2 ) break;
}
stack.push_back(x);
}
int main()
{
F>>n;
for (int i=1;i<=n;++i)
{
double x,y;
F>>x>>y;
points.push_back( make_point(x,y) );
}
sort(points.begin(),points.end(),cmp);
stack.push_back( points[0] );
for (int i=1;i<n;++i)
if ( ecu(points[0],points[n-1],points[i]) || i == n-1 )
add(points[i]);
hull = stack;
hull.pop_back();
stack.clear();
stack.push_back(points[n-1]);
for (int i=n-1;i>=0;--i)
if ( ecu(points[n-1],points[0],points[i]) || i == 0 )
add(points[i]);
for (int i=0;i<int(stack.size())-1;++i)
hull.push_back(stack[i]);
G<<hull.size()<<'\n';
for (int i=0;i<hull.size();++i)
G<<fixed<<setprecision(6)<<hull[i].x<<' '<<hull[i].y<<'\n';
}