Pagini recente » Cod sursa (job #1254734) | Cod sursa (job #712749) | Cod sursa (job #2333739) | Cod sursa (job #1208124) | Cod sursa (job #1188390)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
const int MAX = 130000;
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coada{
double x,y;
};
coada q[MAX],st[MAX];
double determin(coada a,coada b,coada c){
return static_cast<double> (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(coada a,coada b){
return determin(q[1],a,b)>0;
}
int n,nr;
int main(){
fin>>n;
fin>>q[1].x>>q[1].y;
for(int i=2;i<=n;++i){
fin>>q[i].x>>q[i].y;
if(q[1].x>q[i].x or(q[1].x==q[i].x and q[1].y>q[i].y))swap(q[1],q[i]);
}
sort(q+2,q+n+1,cmp);
st[++nr]=q[1];
st[++nr]=q[2];
for(int i=3;i<=n;++i){
while(determin(st[nr],st[nr-1],q[i])>0 and nr>=2)--nr;
st[++nr]=q[i];
}
fout<<nr<<'\n';
for(int i=1;i<=nr;++i)fout<<fixed<<setprecision(12)<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}