Pagini recente » Cod sursa (job #1244489) | Cod sursa (job #826197) | Cod sursa (job #3322903) | Cod sursa (job #3341376) | Cod sursa (job #3300689)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
long double x, y;
};
long double distPoints(Point A, Point B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
int turn(Point p, Point c, Point n){
long double x = (c.x - p.x) * (n.y - p.y) - (c.y - p.y) * (n.x - p.x);
if(x < 0)
return -1;
else if(x > 0)
return 1;
return 0;
}
Point first;
bool polarSort(const Point& A, const Point& B){
int u = turn(first, A, B);
if(u > 0)
return true;
else if(u < 0)
return false;
return distPoints(first, A) < distPoints(first, B);
}
bool compare(const Point& A, const Point& B){
return (A.y < B.y) || (A.y == B.y && A.x < B.x);
}
vector<Point> convex(vector<Point> Points){
vector<Point> infas;
first = *min_element(Points.begin(), Points.end(), compare);
sort(Points.begin(), Points.end(), polarSort);
for(int i = 0; i < Points.size(); i++){
while(infas.size() > 1 && turn(infas[infas.size() - 2], infas[infas.size() - 1], Points[i]) <= 0)
infas.pop_back();
infas.push_back(Points[i]);
}
return infas;
}
int main()
{
int n;
Point tempPoint;
fin >> n;
vector<Point> Points, infas;
for(int i = 0; i < n; i++){
fin>> tempPoint.x >> tempPoint.y;
Points.push_back(tempPoint);
}
infas = convex(Points);
fout << infas.size() << '\n';
for(int i = 0; i < infas.size(); i++){
fout << fixed << setprecision(12) << infas[i].x << " " << infas[i].y << '\n';
}
fin.close();
fout.close();
return 0;
}