Pagini recente » Cod sursa (job #1044422) | Cod sursa (job #2675318) | Cod sursa (job #1000405) | Cod sursa (job #1539623) | Cod sursa (job #1796541)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
class Punct {
public:
double x;
double y;
bool in_infasuratoare;
Punct(double x, double y) {
this->x = x;
this->y = y;
this->in_infasuratoare = false;
}
Punct() {
this->x = this->y = 0;
this->in_infasuratoare = false;
}
bool semn(Punct a, Punct b) {
double semn = a.x * b.y + b.x * y + x * a.y - a.y * b.x - b.y * x - y * a.x;
return semn < 0;
}
friend bool operator<(const Punct& p1, const Punct& p2);
friend istream& operator>>(istream& is, Punct& p);
friend ostream& operator<<(ostream& os, const Punct& p);
};
bool operator<(const Punct& p1, const Punct& p2) {
if (p1.y == p2.y) return p1.x < p2.x;
return p1.y < p2.y;
}
istream& operator>>(istream& is, Punct& p) {
is >> p.x >> p.y;
return is;
}
ostream& operator<<(ostream& os, Punct& p) {
os << fixed << setprecision(6) << p.x << ' ' << p.y;
return os;
}
class Figura {
private:
vector <Punct> punct;
vector <Punct> infasuratoare;
public:
vector <Punct> get_infasuratoare() {
if (infasuratoare.size() != 0) return infasuratoare;
vector <int> stiva;
int n = (int)punct.size();
sort(punct.begin(), punct.end());
stiva.push_back(0);
punct[0].in_infasuratoare = false;
stiva.push_back(1);
punct[1].in_infasuratoare = false;
int top = 1;
int pas = 1;
for (int i = 2; i >= 0; i+= pas) {
if (i == n - 1) pas = -1;
if (!punct[i].in_infasuratoare) {
while(top >= 1 && punct[i].semn(punct[stiva[top - 1]], punct[stiva[top]])) {
punct[stiva[top]].in_infasuratoare = false;
stiva.pop_back();
top--;
}
top++;
stiva.push_back(i);
punct[i].in_infasuratoare = true;
}
}
for (vector <int> :: iterator it = stiva.begin(); it != stiva.end(); it++) {
infasuratoare.push_back(punct[*it]);
}
infasuratoare.pop_back();
return infasuratoare;
}
friend istream& operator>>(istream& is, Figura& f);
};
istream& operator>>(istream& is, Figura& f) {
int n;
Punct p;
is >> n;
for (int i = 0; i < n; i++) {
is >> p;
f.punct.push_back(p);
}
f.get_infasuratoare();
return is;
}
int main() {
Figura figura;
f >> figura;
vector <Punct> infasuratoare = figura.get_infasuratoare();
g << infasuratoare.size() << '\n';
for (vector <Punct> :: iterator it = infasuratoare.begin(); it != infasuratoare.end(); it++) {
g << *it << '\n';
}
g << '\n';
return 0;
}