Pagini recente » Cod sursa (job #1095524) | Cod sursa (job #3277352) | Cod sursa (job #1769779) | Cod sursa (job #1646403) | Cod sursa (job #387084)
Cod sursa(job #387084)
//Graham scan in O(NlogN)
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
const char RMode[]="r";
const char WMode[]="w";
const long int MaxN=10005;
const double PI=3.1415926536;
struct p2d{
double x,y;
};
vector<p2d> p,c;
p2d t;
long int n;
FILE *f;
ifstream fin(InFile);
ofstream fout(OutFile);
double PolarAngle(p2d P, p2d Q){
double angle=atan2(Q.y-P.y,Q.x-P.x);
if(angle<0){
angle+=PI*2;
}
return angle;
}
typedef pair<p2d, double> polar_point;
bool polar_point_cmp(const polar_point& left, const polar_point& right){
return left.second<right.second;
}
inline double det(p2d p1, p2d p2, p2d p3){
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
inline bool good(p2d p1, p2d p2, p2d p3){
return det(p1,p2,p3)>0;
}
int main(){
f=fopen(InFile,RMode);
fscanf(f,"%ld",&n);
fin>>n;
for(register int i=0;i<n;++i){
fin>>t.x>>t.y;
p.push_back(t);
}
fin.close();
p2d ext;
int ind=0;
ext=p[0];
for(register long int i=1;i<(long int)p.size();++i){
if(ext.y>p[i].y || (ext.y==p[i].y && ext.x>p[i].x)){
ext=p[i];
ind=i;
}
}
p.erase(p.begin()+ind);
c.push_back(ext);
vector<polar_point> s;
for(register long int i=0;i<(long int)p.size();++i){
s.push_back(polar_point(p[i],PolarAngle(c[0],p[i])));
}
sort(s.begin(),s.end(),polar_point_cmp);
c.push_back(s[0].first);
c.push_back(s[1].first);
for(register long int i=2;i<(long int)s.size();++i){
p2d p_i=s[i].first;
p2d p_i1=c[c.size()-1];
p2d p_i2=c[c.size()-2];
while(!good(p_i2,p_i1,p_i)){
c.erase(c.end()-1);
p_i1=p_i2;
p_i2=c[c.size()-2];
}
c.push_back(p_i);
}
fout<<c.size()<<"\n";
for(register long int i=0;i<(long int)c.size();++i){
fout<<setprecision(6)<<c[i].x<<" "<<c[i].y<<"\n";
}
fout.close();
return 0;
}