Pagini recente » Cod sursa (job #1551623) | Cod sursa (job #104059) | Cod sursa (job #385585) | Cod sursa (job #1282869) | Cod sursa (job #1776293)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define hs h.size()
#define vs v.size()
using namespace std;
struct point {
double x, y;
};
vector<point> v, h;
double det(point a, point b, point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool CP(point a, point b)
{
return (a.x<b.x)||(a.x==b.x)&&(a.y<b.y);
}
bool CA(point a, point b)
{
return det(v[0], a, b) < 0;
}
void hull()
{
swap(v[0], *min_element(v.begin(), v.end(), CP));
sort(v.begin()+1, v.end(), CA);
h.push_back(v[0]);
h.push_back(v[1]);
for (int i = 2; i < vs; i++) {
while (hs>1 && det(h[hs-2], h[hs-1], v[i])>0)
{
h.pop_back();
}
h.push_back(v[i]);
}
reverse(h.begin(), h.end());
}
void read()
{
ifstream cin("infasuratoare.in");
int n;
cin>>n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin>>v[i].x>>v[i].y;
}
}
void write()
{
ofstream cout("infasuratoare.out");
cout<<fixed;
cout<<hs<<"\n";
for (int i = 0; i<hs; i++)
{
cout<<setprecision(9)<<h[i].x<<" "<<h[i].y<<"\n";
}
}
int main()
{
read();
hull();
write();
return 0;
}