Pagini recente » Cod sursa (job #346008) | Cod sursa (job #1264256) | Cod sursa (job #3153722) | Cod sursa (job #3198292) | Cod sursa (job #2535660)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct{
double x, y;
punct(double cx = 0, double cy = 0){
this->x = cx;
this->y = cy;
}
bool operator<(const punct &other) const {
if(this->x == other.x){
return this->y < other.y;
}
return this->x < other.x;
}
};
int n;
vector<pair<punct, bool>> puncte;
bool intoarcere(punct a, punct b, punct c){
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) >= 0;
}
void citire(){
ifstream f("infasuratoare.in");
f>>n;
for (int i = 0; i < n; ++i) {
puncte.emplace_back();
f>>puncte[i].first.x>>puncte[i].first.y;
puncte[i].second = false;
}
}
vector<int> build(){
vector<int> result;
result.push_back(0);
result.push_back(1);
puncte[1].second = true;
for (int i = 2; i < n; ++i) {
while(result.size() >= 2 && !intoarcere(puncte[result[result.size() - 2]].first, puncte[result[result.size() - 1]].first, puncte[i].first)){
puncte[result[result.size() - 1]].second = false;
result.pop_back();
}
result.push_back(i);
puncte[i].second = true;
}
for(int i = n - 2; i >= 0; i--){
if(puncte[i].second)
continue;
while(result.size() >= 2 && !intoarcere(puncte[result[result.size() - 2]].first, puncte[result[result.size() - 1]].first, puncte[i].first)){
puncte[result[result.size() - 1]].second = false;
result.pop_back();
}
result.push_back(i);
puncte[i].second = true;
}
result.pop_back();
return result;
}
int main() {
citire();
sort(puncte.begin(), puncte.end());
vector<int> result = build();
ofstream g("infasuratoare.out");
g<<result.size()<<"\n";
g<<setprecision(6)<<fixed;
for (auto & i : result) {
g<<puncte[i].first.x<<' '<<puncte[i].first.y<<"\n";
}
return 0;
}