Pagini recente » Cod sursa (job #1269064) | Cod sursa (job #1018547) | Cod sursa (job #1285288) | Cod sursa (job #1749558) | Cod sursa (job #2432489)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
typedef std::pair<double, double> Point;
#define x first
#define y second
const double ERR = 1e-12;
struct Comp: std::binary_function<Point,Point,bool>
{
bool operator() (Point p1, Point p2)
{
if(p1.y != p2.y)
return p1.y<p2.y;
return p1.x<p2.x;
}
};
int n;
std::vector<std::pair<double, double> >v;
int head;
int stack[120005];
bool vis[120005];
double cross_product(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int main()
{
fin>>n;
std::cout<< std::setprecision(6) << std::fixed;
fout<< std::setprecision(6) << std::fixed;
for(int i=0;i<n;i++)
{
double x,y;
fin>>x>>y;
v.push_back(std::make_pair(x,y));
}
std::sort(v.begin(), v.begin()+n,Comp());
stack[0]=0;
stack[1]=1;
vis[1]=true;
// vis[0]=true;
head=2;
int p=1;
for(int i=1;i>=0;i+=(p= (i==n-1)?-p:p))
{
if (vis[i]) continue;
while(head>=2 && cross_product(v[stack[head-2]],v[stack[head-1]],v[i])<ERR)
{
vis[stack[head-1]]=false;
head--;
}
vis[i]=true;
stack[head]=i;
head++;
}
fout<<head-1<<"\n";
for(int i=0;i<head-1;i++)
fout<<v[stack[i]].x<<" "<<v[stack[i]].y<<"\n";
}