Pagini recente » Cod sursa (job #3238491) | Cod sursa (job #1468399)
#include <fstream>
#include <algorithm>
using namespace std;
const int MAX = 120001;
struct point{
double x, y;
} v[MAX];
int n, sus[MAX], jos[MAX], vsus, vjos;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool cmp(point a, point b){return a.x<b.x or (a.x==b.x and a.y<b.y);}
double cross(point a, point b, point c){
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++) fin>>v[i].x>>v[i].y;
sort(v+1, v+n+1, cmp);
sus[++vsus] = jos[++vjos] = 1;
for(int i=2; i<=n; i++)
if(cross(v[1], v[n], v[i])<0){
while(vjos>=2 and cross(v[jos[vjos-1]], v[jos[vjos]], v[i])<0)
vjos--;
jos[++vjos] = i;
}
else{
while(vsus>=2 and cross(v[sus[vsus-1]], v[sus[vsus]], v[i])>0)
vsus--;
sus[++vsus] = i;
}
fout.precision(6); fout<<fixed;
for(int i=1; i<=vjos; i++)
fout<<v[jos[i]].x<<' '<<v[jos[i]].y<<'\n';
for(int i=vsus; i>1; i--)
fout<<v[sus[i]].x<<' '<<v[sus[i]].y<<'\n';
return 0;
}