Pagini recente » Cod sursa (job #1029391) | Cod sursa (job #1029384) | Cod sursa (job #958620) | Cod sursa (job #2585768) | Cod sursa (job #251268)
Cod sursa(job #251268)
#include<fstream>
#include<algorithm>
using namespace std;
struct Punct {
double x, y;
}a[120009];
int Stiva[120009],vf=-1;
bool viz[120009];
int cmp(Punct a, Punct b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
void coeficienti(Punct a, Punct b, double& aa, double& bb, double& cc){
aa=a.y-b.y;
bb=b.x-a.x;
cc=b.y*a.x-b.x*a.y;
}
char semn(int gh){
double aa, bb, cc;
coeficienti(a[Stiva[vf-1]], a[Stiva[vf]], aa, bb, cc);
if(aa*a[gh].x+bb*a[gh].y+cc>=0)
return '+';
return '-';
}
int main(){
int i, n;
ifstream f("infasuratoare.in");
f>>n;
for(i=0;i<n;i++)
f>>a[i].x>>a[i].y;
f.close();
sort(a, a+n, cmp);
Stiva[++vf]=0;
Stiva[++vf]=1;
viz[0]=1;
viz[1]=1;
for(i=2;i<n&&a[i].y>=a[i-1].y;i++){
while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
viz[Stiva[++vf]=i]=1;
}
for(i=n-1;i>=0;i--)
if(!viz[i]){
while(vf>0&&semn(i)=='-') viz[Stiva[vf--]]=0;
viz[Stiva[++vf]=i]=1;
}
while(semn(0)=='-') --vf;
ofstream g("infasuratoare.out");
g<<vf+1<<'\n';
for(i=0;i<=vf;i++) g<<a[Stiva[i]].x<<' '<<a[Stiva[i]].y<<'\n';
g.close();
return 0;
}