Pagini recente » Cod sursa (job #431173) | Cod sursa (job #2427743) | Cod sursa (job #1519441) | Cod sursa (job #285868) | Cod sursa (job #2955883)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int MAXN = 120000;
const int INF = 10e8;
struct point{
double x, y;
};
point points[MAXN];
int noPoints;
vector<point> polygon;
int getStartPoint(){
int i, index;
index = 0;
for( i = 0; i < noPoints; i++ ){
if( points[index].y > points[i].y )
index = i;
else if( points[index].y == points[i].y && points[index].x > points[i].x )
index = i;
}
return index;
}
double getOrientation( point a, point b, point c ){
return ( b.y - a.y ) * ( c.x - b.x ) - ( c.y - b.y ) * ( b.x - a.x );
}
bool cmp( point a, point b ){
return getOrientation(points[0], a, b) < 0;
}
void getPolygon(){
int i;
polygon.push_back(points[0]);
polygon.push_back(points[1]);
for( i = 2; i < noPoints; i++ ){
while( polygon.size() >= 2 && getOrientation( polygon[polygon.size() - 2], polygon[polygon.size() - 1], points[i] ) >= 0 )
polygon.pop_back();
polygon.push_back(points[i]);
}
}
int main()
{
int i;
in>>noPoints;
for( i = 0; i < noPoints; i++ ){
in>>points[i].x>>points[i].y;
//out<<points[i].x<<" "<<points[i].y<<'\n';
}
//out<<getStartPoint()<<'\n';
swap(points[getStartPoint()], points[0]);
sort(points + 1, points + noPoints, cmp);
getPolygon();
out<<polygon.size()<<'\n';
for( i = 0; i < polygon.size(); i++ ){
out<<fixed<<setprecision(6)<<polygon[i].x<<" "<<polygon[i].y<<'\n';
}
return 0;
}