Pagini recente » Cod sursa (job #77920) | Cod sursa (job #1779620) | Cod sursa (job #626072) | Cod sursa (job #1600147) | Cod sursa (job #1409507)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
typedef pair<double, double> Point;
#define NMax 120005
#define eps 1e-12
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
Point v[NMax];
bool viz[NMax];
int st[NMax], head;
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);
}
void solve(int i)
{
while(head >= 2 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < eps)
viz[st[head--]] = false;
st[++head] = i;
viz[i] = true;
}
int main()
{
int i;
f>>n;
for(i=1;i<=n;++i) f>>v[i].x>>v[i].y;
sort(v+1,v+n+1);
st[1] = 1; st[2] = 2; head = 2;
viz[2] = true;
for(i=3;i<n;++i) if(!viz[i]) solve(i);
for(i=n;i>=1;--i) if(!viz[i]) solve(i);
g<<head-1<<"\n";
g<<setprecision(6)<<fixed;
for(i=1;i<head;++i) g<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
f.close();
g.close();
}