Pagini recente » Cod sursa (job #1060129) | Cod sursa (job #2118061) | Cod sursa (job #1330791) | Monitorul de evaluare | Cod sursa (job #3310226)
#include <ios>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;
struct Punct {
double x, y;
Punct operator-(const Punct &p) const {
return {x - p.x, y - p.y};
}
Punct operator+(const Punct &p) const {
return {x + p.x, y + p.y};
}
Punct operator*(double t) const {
return {x * t, y * t};
}
double operator^(const Punct &p) const {
return x*p.y - y*p.x;
}
};
vector<Punct> infasuratoare(vector<Punct> poligon) {
map<double, Punct> p;
int imn;
Punct mn{10e12, 10e12};
for(int i=0; i<poligon.size(); ++i) {
auto &punct = poligon[i];
if(punct.y < mn.y || (punct.y == mn.y && punct.x < mn.x)) {
mn = punct;
imn = i;
}
}
for(int i=0; i<poligon.size(); ++i) {
auto &punct = poligon[i];
if(imn != i) {
double unghi = atan2(punct.y-mn.y, punct.x-mn.x);
if(!p.count(unghi)) {
p[unghi] = punct;
} else {
double d1 = (p[unghi].x-mn.x)*(p[unghi].x-mn.x) + (p[unghi].y-mn.y)*(p[unghi].y-mn.y);
double d2 = (punct.x-mn.x)*(punct.x-mn.x) + (punct.y-mn.y)*(punct.y-mn.y);
if(d2 > d1) {
p[unghi] = punct;
}
}
}
}
vector<Punct> stiva;
stiva.push_back(mn);
for(auto &[unghi, punct] : p) {
while(stiva.size() >= 2) {
Punct A = stiva[stiva.size()-2];
Punct B = stiva[stiva.size()-1];
long double k = (B.x - A.x)*(punct.y - A.y) - (B.y - A.y)*(punct.x - A.x);
if(k <= 0) {
stiva.pop_back();
} else {
break;
}
}
stiva.push_back(punct);
}
return stiva;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fout << fixed << setprecision(6);
int N;
fin >> N;
vector<Punct> pt(N);
for(int i=0; i<N; ++i) {
fin >> pt[i].x >> pt[i].y;
}
auto cpt = infasuratoare(pt);
fout << cpt.size() << '\n';
for(auto p: cpt) {
fout << p.x << ' ' << p.y << '\n';
}
return 0;
}