Pagini recente » Cod sursa (job #2562459) | Cod sursa (job #3180281) | Cod sursa (job #2920905) | Cod sursa (job #3163355) | Cod sursa (job #1783102)
// CTI
// Infasuratoarea convexa
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
class Point {
public:
double x;
double y;
};
Point x;
vector <Point> v;
double delta(Point p,Point q, Point r) {
/*
|q.x - p.x r.x - p.x| - matricea
|q.y - p.y r.y - p.y|
*/
double x = (q.x - p.x) * (r.y - p.y) - (r.x - p.x) * (q.y - p.y);
return x;
}
bool compare(Point p, Point q) {
double d = delta(x, p, q);
if (d < 0) {
return true;
}
return false;
}
void infasuratoareConvexa()
{
// citim datele
int n; f >> n;
v.push_back(x); // push sa incepem de la 1
for (int i = 1; i <= n; ++i) {
Point Po;
f >> Po.x >> Po.y;
v.push_back(Po);
}
// aflam un punct care se afla sigur pe infasuratoare
int k = 1; // presupunem ca primul se afla
for (int i = 2; i <= n; ++i) {
if (v[k].x > v[i].x) {
k = i;
} else if (v[k].x == v[i].x && v[k].y > v[i].y) {
k = i;
}
}
swap(v[k], v[1]);
x = v[1];
sort (v.begin() + 2, v.end(), compare); // il lasam pe primul pe pozitia lui
vector <Point> s; // vector pentru a verfica daca punctele sunt pe infasuratoare
s.push_back(x); // se afla sigur pe infasuratoare
s.push_back(v[2]); // presupunem ca se afla pe infasuratoare
for (int i = 3; i <= n; ++i) {
int sz = s.size();
x = v[i];
if (sz >= 2 && delta(s[sz - 2], s[sz - 1], x) > 0) { // viraj
while (sz >= 2 && delta(s[sz - 2], s[sz - 1], x) > 0) {
s.pop_back();
sz = s.size();
}
}
s.push_back(v[i]);
}
g << s.size() << '\n';
for (int i = s.size() - 1; i >= 0; --i) {
g << s[i].x << " " << s[i].y << '\n';
}
}
int main()
{
infasuratoareConvexa();
return 0;
}