Pagini recente » Cod sursa (job #1213232) | Cod sursa (job #2417853) | Cod sursa (job #1036828) | Cod sursa (job #2607223) | Cod sursa (job #1728002)
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 120000;
struct point
{
double x;
double y;
};
point p[MAXN+1], pivot;
int n;
vector <point> hull;
void readData()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
}
/*
inline double cross_product(const point& A, const point& B, const point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const point& p1, const point& p2) {
return cross_product(p[1], p1, p2) < 0;
}*/
double crossProduct(point p1, point p2, point p3)
{
double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y, x3 = p3.x, y3 = p3.y;
return x1*y2 + x2*y3 + x3*y1 - x3*y2 - x1*y3 - x2*y1;
}
bool cmp(point p1, point p2)
{
return crossProduct(p[1],p1,p2) < 0;
}
void grahamScan()
{
pivot = p[1];
int pivotPosition= 1;
for(int i = 2; i <= n; i++)
if(pivot.y > p[i].y)
{
pivot = p[i];
pivotPosition = i;
}
else
if(pivot.y == p[i].y)
if(pivot.x > p[i].x)
{
pivot = p[i];
pivotPosition = i;
}
swap(p[1],p[pivotPosition]);
sort(p+2,p+n+1,cmp);
for (int i = 1; i<=n;i++)
cout<<p[i].x<<" "<<p[i].y<<endl;
cout<<endl;
hull.push_back(pivot);
hull.push_back(p[2]);
for(int i = 3; i <= n; i++)
{
while(hull.size() >= 2 && crossProduct(hull[hull.size()-2],hull[hull.size()-1],p[i]) > 0)
hull.pop_back();
hull.push_back(p[i]);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
readData();
grahamScan();
cout<<fixed;
cout<<setprecision(9)<<hull.size()<<endl;
for(int i = hull.size() - 1; i >= 0; i--)
cout<<hull[i].x<<' '<<hull[i].y<<endl;
//testCrossPorduct();
return 0;
}