Pagini recente » Cod sursa (job #1294943) | Cod sursa (job #1603566) | Cod sursa (job #584003) | Cod sursa (job #165786) | Cod sursa (job #2394145)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#define NMAX 120000
#define VMAX 1000000000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,start,minx=VMAX+1,miny=VMAX+1,indici[NMAX+5],i1,i2,rez[NMAX+5],nrez;
pair <double,double> puncte[NMAX+5];
double c1,c2,c3,c4;
stack <int> stiva;
bool criteriu(int a,int b){
if(a==start){
return true;
}else if(b==start){
return false;
}
c1=puncte[a].first-puncte[start].first;
c2=puncte[b].first-puncte[start].first;
c3=puncte[a].second-puncte[start].second;
c4=puncte[b].second-puncte[start].second;
if(c1<=0&&c2>=0){
return false;
}else if(c1>=0&&c2<=0){
return true;
}else if(c1>0&&c2>0){
return c1*c1*(c2*c2+c4*c4)>c2*c2*(c1*c1+c3*c3);
}else{
return c1*c1*(c2*c2+c4*c4)<c2*c2*(c1*c1+c3*c3);
}
}
bool ok(int i){
return (puncte[i1].first*puncte[i2].second+puncte[i2].first*puncte[i].second+puncte[i].first*puncte[i1].second-puncte[i].first*puncte[i2].second-puncte[i].second*puncte[i1].first-puncte[i2].first*puncte[i1].second)>0;
}
int main() {
f>>n;
for(int i=1;i<=n;i++){
f>>puncte[i].first>>puncte[i].second;
if(puncte[i].second<miny){
miny=puncte[i].second;
minx=puncte[i].first;
start=i;
}else if(puncte[i].second==miny&&minx>puncte[i].first){
minx=puncte[i].first;
start=i;
}
indici[i]=i;
}
sort(indici+1,indici+n+1,criteriu);
indici[n+1]=start;
stiva.push(start);
stiva.push(indici[2]);
for(int i=3;i<=n+1;i++){
i2=stiva.top();
stiva.pop();
i1=stiva.top();
if(ok(indici[i])){
stiva.push(i2);
}
stiva.push(indici[i]);
}
while(!stiva.empty()){
rez[++nrez]=stiva.top();
stiva.pop();
}
nrez--;
g<<nrez<<'\n';
for(int i=nrez+1;i>=2;i--){
g<<fixed<<setprecision(12)<<puncte[rez[i]].first<<' '<<puncte[rez[i]].second<<'\n';
}
f.close();
g.close();
return 0;
}