Pagini recente » Cod sursa (job #2349801) | Cod sursa (job #1961974) | Cod sursa (job #148307) | Cod sursa (job #2580388) | Cod sursa (job #2957004)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {
double x, y;
};
int N;
vector <point> v;
bool comp(point A, point B) {
if((A.y - v[0].y) * (B.x - A.x) <= (B.y - A.y) * (A.x - v[0].x))
return true;
return false;
}
bool ok(point A, point B, point C) {
if((B.y - A.y) * (C.x - B.x) <= (C.y - B.y) * (B.x - A.x))
return true;
return false;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++) {
double x, y;
fin >> x >> y;
v.push_back({x, y});
}
// aflam care e P (punctul de plecare)
int idxP = 0;
double minX = 2000000000, minY = 2000000000;
for(int i = 0; i < v.size(); i++)
if(minX > v[i].x || (minX == v[i].x && minY > v[i].y)) {
minX = v[i].x;
minY = v[i].y;
idxP = i;
}
swap(v[0], v[idxP]);
// sortam restul punctelor dupa unghiul pe care il formeaza cu P
sort(&v[1], &v[v.size()], comp);
vector<point> stk;
stk.push_back(v[0]);
stk.push_back(v[1]);
for(int i = 2; i < v.size(); i++) {
while(!ok(stk[stk.size() - 2], stk[stk.size() - 1], v[i])) {
stk.pop_back();
}
stk.push_back(v[i]);
}
fout << stk.size() << '\n';
for(int i = 0; i < stk.size(); i++)
fout << fixed << setprecision(6) << stk[i].x << ' ' << stk[i].y << '\n';
return 0;
}