Pagini recente » Cod sursa (job #961317) | Cod sursa (job #3220439) | Cod sursa (job #2601421) | Cod sursa (job #2465680) | Cod sursa (job #1452895)
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
struct point{
double x,y;
};
int N; point a[125000],stack[125000];
double c_product(point A,point B,point C){
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline bool cmp(point A, point B){
return c_product(a[1],A,B)<0;
}
int main(){
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> N;
int i,pos=1;
for (i=1; i<=N; i++){
fin >> a[i].x >> a[i].y;
if (a[i].x<a[pos].x)
pos=i;
}
swap(a[1],a[pos]);
sort(a+2,a+N+1,cmp);
stack[1]=a[1];
stack[2]=a[2];
int r=2;
for (i=3; i<=N; i++){
while (r>=2 && c_product(stack[r-1],stack[r],a[i])>0)
r--;
stack[++r]=a[i];
}
fout << r << "\n";
for (i=r; i>0; i--)
fout << fixed << setprecision(7) << stack[i].x << " " << stack[i].y << "\n";
return 0;
}