Pagini recente » Cod sursa (job #923477) | Cod sursa (job #640813) | Cod sursa (job #127339) | Cod sursa (job #510157) | Cod sursa (job #2491942)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
float x, y;
};
bool compara(punct a, punct b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
bool cw(punct a, punct b, punct c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}
bool ccw(punct a, punct b, punct c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}
void infasuratoare(vector<punct>& v) {
int i;
if (v.size() == 1)
return;
sort(v.begin(), v.end(), &compara);
punct minim = v[0], maxim = v.back();
vector<punct> sus, jos;
sus.push_back(minim);
jos.push_back(minim);
for (i = 1; i < (int)v.size(); i++) {
if (i == v.size() - 1 || cw(minim, v[i], maxim)) {
while (sus.size() >= 2 && !cw(sus[sus.size() - 2], sus[sus.size() - 1], v[i]))
sus.pop_back();
sus.push_back(v[i]);
}
if (i == v.size() - 1 || ccw(minim, v[i], maxim)) {
while (jos.size() >= 2 && !ccw(jos[jos.size() - 2], jos[jos.size() - 1], v[i]))
jos.pop_back();
jos.push_back(v[i]);
}
}
v.clear();
for (i = 0; i < (int)sus.size(); i++)
v.push_back(sus[i]);
for (i = (int)jos.size() - 2; i > 0; i--) // jos.size() - 1 e B, iar jos[0] e A care au fost tiparite
v.push_back(jos[i]); // in for-ul pentru vectorul sus
}
int main() {
int n, i;
punct p;
vector<punct> v;
fin >> n;
for (i = 1; i <= n; i++) {
fin >> p.x >> p.y;
v.push_back(p);
}
infasuratoare(v);
fout << fixed << setprecision(6);
fout << v.size() << '\n';
for (i = (int)v.size() - 1; i >= 0; i--)
fout << v[i].x << ' ' << v[i].y << '\n';
fin.close();
fout.close();
return 0;
}