Pagini recente » Cod sursa (job #1390649) | Cod sursa (job #2648315) | Cod sursa (job #2678832) | Cod sursa (job #2534374) | Cod sursa (job #1113520)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
struct COORD{ long double x,y; };
inline long double mycrossproduct(const COORD &p1, const COORD &p2, const COORD &p3){
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
COORD primul_punct;
inline bool comp_unghi(const COORD &a, const COORD &b){
return mycrossproduct(primul_punct,a,b)<0;
}
int main(){
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
unsigned n; fin>>n;
std::vector<COORD> puncte(n);
for(unsigned i=0;i<n;++i) fin>>puncte[i].x>>puncte[i].y;
unsigned pos=0;
for(unsigned i=1;i<n;++i)
if(puncte[i].x<puncte[pos].x || ((puncte[i].x==puncte[pos].x)&&(puncte[i].y<puncte[pos].y)))
pos=i;
primul_punct=puncte[pos];
COORD temp=puncte[0]; puncte[0]=primul_punct; puncte[pos]=temp;
std::sort(puncte.begin()+1,puncte.end(),comp_unghi);
std::vector<COORD> st(n);
st[0]=puncte[0]; st[1]=puncte[1];
unsigned top=1;
for(unsigned i=2;i<n;++i){
while(top>0 && mycrossproduct(st[top-1],st[top],puncte[i])>0) --top;
st[++top]=puncte[i];
}
fout<<(top+1)<<"\n";
fout<<std::fixed<<std::setprecision(6);
for(int i=top;i>=0;--i) fout<<st[i].x<<" "<<st[i].y<<"\n";
fout.close();
}