Pagini recente » Cod sursa (job #298903) | Cod sursa (job #2475888) | Cod sursa (job #259284) | Cod sursa (job #1468225) | Cod sursa (job #530557)
Cod sursa(job #530557)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 130000;
ifstream fin("infasuratoare.in");
int i , j , n , m , ind[maxn] , cnt , first;
double minY = 1000000001 , minX;
struct point {
double x , y;
}p[maxn];
bool cmp ( int i , int j) {
return ((p[i].x - p[first].x) * (p[j].y - p[first].y) < (p[j].x - p[first].x) * (p[i].y - p[first].y));
}
double rotateLeft ( point A , point B , point C ) {
double det = A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x;
return det;
}
int main()
{
freopen("infasuratoare.out","w",stdout);
fin >> n;
for( i = 1 ; i <= n ; ++i ) {
fin >> p[i].x >> p[i].y;
if( p[i].y < minY || (p[i].y == minY && p[i].x < minX )) {
first = i;
minY = p[i].y;
minX = p[i].x;
}
}
for( i = 1 ; i <= n ; ++i )
if ( p[i].x != p[first].x || p[i].y != p[first].y )
ind[++cnt] = i;
sort(ind + 1, ind + cnt + 1, cmp);
vector < int > S;
S.push_back(first);
//S.push_back(p[2]);
//S.push_back(p[3]);
for( i = 1; i <= cnt ; ++i ) {
for( ;S.size() >= 2 && rotateLeft(p[S[S.size() - 2]] , p[S[S.size() - 1]] , p[ind[i]]) > 0 ; )
S.pop_back();
S.push_back(ind[i]);
}
printf("%d\n",S.size());
printf("%lf %lf\n",p[first].x,p[first].y);
for(i = S.size() - 1; i >= 1 ; --i )
printf("%lf %lf\n",p[S[i]].x,p[S[i]].y);
return 0;
}