Pagini recente » Cod sursa (job #2075590) | Cod sursa (job #2362606) | Cod sursa (job #1037958) | Cod sursa (job #1657860) | Cod sursa (job #2659644)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct point{
double x, y;
point(double x, double y){
this->x = x;
this->y = y;
}
bool operator<(const point &other) const {
if(this->x < other.x)
return true;
else if(this->x == other.x)
return this->y < other.y;
else return false;
}
bool operator!= (const point &other) const {
if(this->x == other.x && this->y == other.y)
return false;
return true;
}
};
double determinant(point a, point b, point c){
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
f>>n;
vector<point> p;
for (int i = 0; i < n; ++i) {
double x, y;
f>>x>>y;
p.emplace_back(x, y);
}
sort(p.begin(), p.end());
vector<point> v1;
v1.push_back(p[0]);
v1.push_back(p[1]);
for (int i = 2; i < n; ++i) {
if(v1.size() > 1){
if(determinant(v1[v1.size() - 2], v1[v1.size() - 1], p[i]) >= 0){
v1.push_back(p[i]);
}else{
v1.pop_back();
i--;
}
}else v1.push_back(p[i]);
}
reverse(p.begin(), p.end());
vector<point> v2;
v2.push_back(p[0]);
v2.push_back(p[1]);
for (int i = 2; i < n; ++i) {
if(v2.size() > 1){
if(determinant(v2[v2.size() - 2], v2[v2.size() - 1], p[i]) >= 0){
v2.push_back(p[i]);
}else{
v2.pop_back();
i--;
}
}else v2.push_back(p[i]);
}
g<<v1.size() + v2.size() - 2<<"\n";
for (int i = 0; i < v1.size(); ++i) {
g<<v1[i].x<<' '<<v1[i].y<<'\n';
}
for (int i = 1; i < v2.size() - 1; ++i) {
g<<v2[i].x<<' '<<v2[i].y<<'\n';
}
return 0;
}