Pagini recente » Cod sursa (job #2834006) | Cod sursa (job #1607578) | Cod sursa (job #1335683) | Cod sursa (job #1016328) | Cod sursa (job #2140170)
#include <stack>
#include <iomanip>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;
struct Point{
double x,y;
}points[nmax];
Point p0;
Point nextToTop(stack<Point> &S){
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);
return res;
}
void Swap(Point &p1, Point &p2){
Point aux = p1;
p1 = p2;
p2 = aux;
}
double distSq(Point p1, Point p2){
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
int orientation(Point p, Point q, Point r){
double val = (q.y - p.y)*(r.x - q.x) - (q.x - p.x)*(r.y - q.y);
if(val == 0)return 0;
return (val > 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 (distSq(p0,*p2) >= distSq(p0,*p1)) ? -1 : 1;
return (o == 2) ? -1 : 1;
}
void printStack(stack<Point> &S){
Point p = S.top();
S.pop();
if(!S.empty())printStack(S);
g<<setprecision(6)<<fixed<<p.x<<" "<<p.y<<'\n';
}
void Graham(int n, Point points[]){
double ymin = points[0].y;
int min = 0;
for(int i=1;i<n;++i)
{
int y = points[i].y;
if((y < ymin) || (y == ymin && points[i].x < points[min].x)){
min = i;
ymin = y;
}
}
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){g<<"IMPOSIBIL\n"; return;}
stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for(int i = 3; i < n; ++i)
{
while(orientation(nextToTop(S),S.top(),points[i]) != 2)
S.pop();
S.push(points[i]);
}
g<<S.size()<<'\n';
printStack(S);
}
int main(){
int n;
f>>n;
for(int i=0;i<n;++i)
f>>points[i].x>>points[i].y;
Graham(n,points);
return 0;
}