Pagini recente » Cod sursa (job #2947594) | Cod sursa (job #2809086) | Cod sursa (job #1276860) | Cod sursa (job #1383444) | Cod sursa (job #3124098)
#include <fstream>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <stack>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
int n;
class Point{
public:
int x = 0, y = 0;
Point() {};
Point(int x, int 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 int 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);
}
int compare(const void* vp1, const void* vp2){
Point* p1 = (Point*) vp1;
Point* p2 = (Point*) vp2;
int o = orientation(p0, *p1, *p2);
if(o == 0)
return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;
return ((o == 2)? -1 : 1);
}
int main(){
fin >> n;
for(int x, y, i = 0; i < n; i++){
fin >> x >> y;
Point point(x, y);
points.push_back(point);
}
int ymin = points[0].y, min = 0;
for(int i = 1; i < n; i++){
if(ymin > points[i].y || (ymin == points[i].y && points[i].x < points[min].x)){
ymin = points[i].y, min = i;
}
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[1], n - 1, sizeof(Point), compare);
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++;
}
if(m < 3)
return 0;
std::stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for(int i = 3; i < m; i++){
while(S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) != 2)
S.pop();
S.push(points[i]);
}
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 << (*it).x << " " << (*it).y << "\n";
}
}