Pagini recente » Cod sursa (job #111376) | Cod sursa (job #1807810) | Monitorul de evaluare | Cod sursa (job #1834367) | Cod sursa (job #530541)
Cod sursa(job #530541)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 130000;
ifstream fin("infasuratoare.in");
int i , j , n , m;
double minY = 1000000001 , minX;
struct point {
double x , y;
}first , p[maxn];
bool cmp (point A, point B) {
return (A.x - first.x) * (B.y - first.y) < (B.x - first.x) * (A.y - 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 = p[i];
minY = p[i].y;
minX = p[i].x;
}
}
sort(p + 1, p + n + 1, cmp);
vector <point> S;
S.push_back(first);
S.push_back(p[2]);
S.push_back(p[3]);
for( i = 4; i <= n ; ++i ) {
for( ;S.size() >= 2 && rotateLeft(S[S.size() - 2] , S[S.size() - 1] , p[i]) > 0 ; )
S.pop_back();
S.push_back(p[i]);
}
printf("%d\n",S.size());
printf("%lf %lf\n",first.x,first.y);
for(i = S.size() - 1; i >= 1 ; --i )
printf("%lf %lf\n",S[i].x,S[i].y);
return 0;
}