Pagini recente » Cod sursa (job #559359) | Cod sursa (job #2175834) | Cod sursa (job #607279) | Cod sursa (job #2664573) | Cod sursa (job #3126401)
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <stack>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int n;
class Point{
public:
long double x = 0, y = 0;
Point() {};
Point(long double x, long double y) : x(x), y(y) {};
friend std::ostream& operator <<(std::ostream& fout, const Point& point){
fout << "(" << point.x << ", " << point.y << ")";
return fout;
}
};
std::vector<Point> points;
Point p0;
Point nextToTop(std::stack<Point>& S){
Point top = S.top();
S.pop();
Point next = S.top();
S.push(top);
return next;
}
void swap(Point& P, Point& Q){
Point temp;
temp = P;
P = Q;
Q = temp;
}
inline long double dist(const Point& P, const Point& Q){
return (Q.x - P.x) * (Q.x - P.x) + (Q.y - P.y) * (Q.y - P.y);
}
int orientation(const Point& P, const Point& Q, const Point& R){
int alpha = (Q.y - P.y) * (R.x - Q.x) - (R.y - Q.y) * (Q.x - P.x);
if(alpha == 0)
return 0;
return ((alpha > 0) ? 1 : 2);
}
bool compare(const Point& p1, const Point& p2){
int o = orientation(p0, p1, p2);
if(o == 0)
return (dist(p0, p2) >= dist(p0, p1)) ? true : false;
return ((o == 2)? true : false);
}
bool ToLeft ( const Point & A, const Point & B, const Point & C )
{
return (( 1LL * B.y - A.y ) * ( C.x - B.x ) < (1LL *C.y - B.y ) * ( B.x - A.x ));
}
bool comp( const Point & B, const Point & C )
{
return ToLeft( points[1], B, C );
}
int main(){
fin >> n;
for(int i = 0; i < n; i++){
long double x, y;
fin >> x >> y;
Point point(x, y);
points.push_back(point);
}
long double xmin = points[0].x;int min = 0;
for(int i = 1; i < n; i++){
if(xmin > points[i].x || (xmin == points[i].x && points[i].y < points[min].y)){
xmin = points[i].x, min = i;
}
}
swap(points[0], points[min]);
p0 = points[0];
std::sort(points.begin() + 1, points.end(), compare);
/*for(auto it : points){
std::cout << it << "\n";
}*/
/*int m = 1;
for(int i = 1; i < n; i++){
while(i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0){
i ++;
}
points[m] = points[i];
m++;
}*/
std::stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for(int i = 3; i < n; i++){
//std::cout << nextToTop(S) << " " << S.top() << " " << points[i] << orientation(nextToTop(S), S.top(), points[i]) <<" " << "\n";
while(S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) != 2){
S.pop();
}
S.push(points[i]);
//std::cout << points[i] << "\n";
}
std::vector<Point> result;
while(!S.empty()){
Point p = S.top();
result.push_back(p);
S.pop();
}
fout << result.size() << "\n";
for(std::vector<Point>::reverse_iterator it = result.rbegin(); it != result.rend(); it ++){
fout << std::fixed << std::setprecision(6) << (*it).x << " " << (*it).y << "\n";
}
}