Pagini recente » Cod sursa (job #1117991) | Cod sursa (job #2757087) | Cod sursa (job #1933134) | Cod sursa (job #2900044) | Cod sursa (job #2116643)
#include<bits/stdc++.h>
#define NMAX 120015
#define x first
#define y second
using namespace std;
typedef pair<double, double>point;
int n,m;
point a[NMAX];
point s[NMAX];
double crossProduct(point A, point B, point C) {
return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
bool cmp(point A, point B) {
return crossProduct(A,B,a[1])<0;
}
void sortAngle() {
int pos=1;
for (int i=2; i<=n; i++) {
if (a[i].x<a[pos].x || a[i].x==a[pos].x && a[i].y<a[pos].y) pos=i;
}
swap(a[1],a[pos]);
sort(a+2, a+1+n, cmp);
}
int main() {
ifstream cin("infasuratoare.out");
ofstream cout("infasuratoare.out");
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i].x>>a[i].y;
}
sortAngle();
s[1]=a[1]; s[2]=a[2]; int last=2;
for (int i=3; i<=n; i++) {
while (crossProduct(s[last-1],s[last],a[i])>0) {
last--;
}
s[++last]=a[i];
}
cout<<last<<'\n';
for (int i=last; i>=1; i--) {
cout<<fixed<<setprecision(13)<<s[i].x<<" "<<s[i].y<<"\n";
}
return 0;
}