Pagini recente » Cod sursa (job #553840) | Cod sursa (job #1175153) | Cod sursa (job #2752095) | Cod sursa (job #1427058) | Cod sursa (job #1296742)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
struct P{
double x,y;
};
P a[120005];
P v[120005];
int n,M;
inline double cross_Product(const P& A,const P& B,const P& C){
return A.x*(B.y - C.y) + B.x*(C.y - A.y) + C.x*(A.y - B.y);
}
inline int comp(const P& A,const P& B){
return cross_Product(a[1],A,B) < 0;
}
void point_sort()
{
int pos = 1;
for(int i = 2; i <= n; i++){
if(a[i].x == a[pos].x){
if(a[i].y < a[pos].y){
pos = i;
}
}
else if(a[i].x < a[pos].x){
pos = i;
}
}
swap(a[1],a[pos]);
sort(a+2,a+n+1,comp);
}
void convex_hull()
{
point_sort();
M = 2;
v[1] = a[1];
v[2] = a[2];
for(int i = 3; i <= n; i++){
while(M >= 2 && cross_Product(v[M-1],v[M],a[i]) > 0)
M--;
v[++M] = a[i];
}
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> n;
for(int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
convex_hull();
fout << M << "\n";
for(int i = M; i >= 1; i--)
fout << fixed << setprecision(12) << v[i].x << " " << v[i].y << "\n";
}