Pagini recente » Cod sursa (job #2960263) | Cod sursa (job #1682273) | Cod sursa (job #1418084) | Cod sursa (job #1824375) | Cod sursa (job #2491940)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pt {
double x, y;
};
bool cmp(pt a, pt b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cw(pt a, pt b, pt c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
bool ccw(pt a, pt b, pt c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
void convex_hull(vector<pt>& a) {
if (a.size() == 1)
return;
sort(a.begin(), a.end(), &cmp);
pt p1 = a[0], p2 = a.back();
vector<pt> up, down;
up.push_back(p1);
down.push_back(p1);
for (int i = 1; i < (int)a.size(); i++) {
if (i == a.size() - 1 || cw(p1, a[i], p2)) {
while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i]))
up.pop_back();
up.push_back(a[i]);
}
if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i]))
down.pop_back();
down.push_back(a[i]);
}
}
a.clear();
for (int i = 0; i < (int)up.size(); i++)
a.push_back(up[i]);
for (int i = down.size() - 2; i > 0; i--)
a.push_back(down[i]);
}
int main()
{
vector<pt> a;
pt P;
int n,i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>P.x>>P.y;
a.push_back(P);
}
convex_hull(a);
fout << fixed << setprecision(6);
fout<<a.size()<<'\n';
for(i=a.size()-1;i>=0;i--)
fout<<a[i].x<<' '<<a[i].y<<'\n';
}