Pagini recente » Cod sursa (job #1277156) | Cod sursa (job #1210178) | Cod sursa (job #822340) | Cod sursa (job #1166868) | Cod sursa (job #1303567)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {double x,y;}v[102],s[102],pmin;
int k,n,i;
double produs(punct p1,punct p2,punct p3){
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int cadran(punct p){
if(p.x>=pmin.x && p.y>=pmin.y)
return 1;
if(p.x<pmin.x && p.y>=pmin.y)
return 2;
if(p.x<pmin.x && p.y<pmin.y)
return 3;
if(p.x>=pmin.x && p.y<pmin.y)
return 4;
}
double distpatrat(punct a){
return (a.x-pmin.x)*(a.x-pmin.x)+(a.y-pmin.y)*(a.y-pmin.y);
}
int cmp(punct a,punct b){
int c1=cadran(a);
int c2=cadran(b);
if(c1>c2)
return 0;
if(c1<c2)
return 1;
if(produs(pmin,a,b)<0)
return 0;
if(produs(pmin,a,b)==0 && distpatrat(a)>distpatrat(b) && c1==c2)
return 0;
return 1;
}
void PUSH(punct x){
s[++k]=x;
}
void POP(){
k--;
}
void afis(){
fout<<k<<'\n';
for(int i=1;i<=k;i++)
fout<<setprecision(6)<<fixed<<v[i].x<<" "<<setprecision(6)<<fixed<<v[i].y<<'\n';
}
void Graham(){
int i;
double o;
sort(v+1,v+n+1,cmp);
k=0;
PUSH(v[1]);
PUSH(v[2]);
for(i=3;i<=n;i++){
o=produs(s[k-1],s[k],v[i]);
if(o==0){
POP();
PUSH(v[i]);
}
else{
if(o>0)
PUSH(v[i]);
else{
while(o<=0 && k>1){
POP();
o=produs(s[k-1],s[k],v[i]);
}
PUSH(v[i]);
}
}
}
afis();
}
int main(){
fin>>n;
pmin.x=3200;
pmin.y=3200;
for(i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
if(v[i].x<=pmin.x && v[i].y<=pmin.y)
pmin=v[i];
}
Graham();
fin.close();fout.close();
return 0;
}