Pagini recente » Cod sursa (job #2951101) | Cod sursa (job #3267327) | Cod sursa (job #2957192) | Cod sursa (job #3212384) | Cod sursa (job #3299478)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120001;
struct ura{
double x,y;
int parte;
}v[NMAX];
double arie(ura a, ura b, ura c){
return a.x*b.y + b.x*c.y + c.x*a.y -b.y*c.x -c.y*a.x - a.y*b.x;
}
int st[NMAX];
bool cmp(ura a, ura b){
if(a.x < b.x){
return true;
}else{
if(a.x == b.x){
if(a.y < b.y){
return true;
}
return false;
}
return false;
}
}
int main() {
int i,n, k;
in>>n;
for(i = 1;i<=n;i++){
in>>v[i].x>>v[i].y;
}
sort(v + 1, v+n+1, cmp);
ura prim = v[1], ultim = v[n];
for(i = 2;i<=n - 1;i++){
if(arie(prim, ultim, v[i]) < 0){
v[i].parte = 2; // dedesubtul dreptei
}else{
v[i].parte = 1; // deasupra dreptei
}
}
st[1] = 1;
k = 1;
for(i = 2;i<=n;i++){ //dedesubt
if(v[i].parte == 2 || v[i].parte == 0){
while(k>1 && arie(v[st[k - 1]], v[st[k]], v[i]) <0){
k--;
}
k++;
st[k]=i;
}
}
int ck = k;
for(i = n-1;i>=1;i--){//deasupra
if(v[i].parte == 1 || v[i].parte == 0){
while(k>ck && arie(v[i], v[st[k]], v[st[k-1]]) > 0){
k--;
}
k++;
st[k]=i;
}
}
out<<k - 1<<"\n";
for(i = 2;i<k;i++){
out<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
out<<fixed<<setprecision(6)<<v[st[1]].x<<" "<<v[st[1]].y<<"\n";
return 0;
}