Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 204 si 223 | Diferente pentru implica-te/arhiva-educationala intre reviziile 215 si 223 | Cod sursa (job #3286545) | Diferente pentru implica-te/arhiva-educationala intre reviziile 193 si 223 | Cod sursa (job #3293374)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x, y;
};
const int N = 12e4;
point p[N + 1];
int st[N + 1];
int n, sz;
double orientation(point a, point b, point c)
{
return (b.x - a.x) * (c.y - b.y) -
(b.y - a.y) * (c.x - b.x);
}
double manhattan(point a, point b){
return fabs(a.x - b.x) + fabs(a.y - b.y);
}
void convex_hull(){
sz = 0;
for(int i = 1; i <= n; i++)
{
while(sz >= 2 && orientation(p[st[sz - 1]], p[st[sz]], p[i]) <= 0)
sz--;
sz++;
st[sz] = i;
}
while(sz > 3 && orientation(p[st[sz - 1]], p[st[sz]], p[1]) <= 0)
sz--;
}
void print_hull(){
fout<<sz<<'\n';
fout<<fixed;
for(int i = 1; i <= sz; i++)
fout<<p[st[i]].x<<' '<<p[st[i]].y<<'\n';
fout<<setprecision(12);
}
bool cmp(point a, point b)
{
double orient = orientation(p[1], a, b);
if(orient == 0) ///a, b, p[1] coliniare
return manhattan(p[1], a) < manhattan(p[1], b); ///choose closer point
return orient > 0; ///order points clockwise
}
void sort_points(){
sort(p + 2, p + n + 1, cmp);
}
void find_lowest(){
int ind = 1;
for(int i = 2; i <= n; i++)
{
if(p[i].x < p[ind].x || (p[i].x == p[ind].x && p[i].y < p[ind].y))
ind = i;
}
swap(p[ind], p[1]);///make first point be the lowest
}
void read(){
fin>>n;
for(int i = 1; i <= n; i++)
fin>>p[i].x>>p[i].y;
}
int main()
{
read();
find_lowest();
sort_points();
convex_hull();
print_hull();
return 0;
}