Pagini recente » Cod sursa (job #2473988) | Cod sursa (job #702332) | Cod sursa (job #1911481) | Cod sursa (job #1174241) | Cod sursa (job #942939)
Cod sursa(job #942939)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define inf 1<<30
#define nmax 120005
#define angle first
#define coord second
using namespace std;
struct point {
double x, y;
};
point temp, source;
vector <pair <double, point> > p;
vector <point> S;
double polar_angle;
point top(vector <point> S) {
return S[S.size()-1];
}
point next_to_top(vector <point> S) {
return S[S.size()-2];
}
//if the ccw of 3 points is positive, then the segment makes a non-left turn
int ccw(point A, point B, point C) {
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
int cmp(pair <double, point> a, pair <double, point> b) {
return(a.angle <= b.angle);
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i, j;
double a, b;
temp.y = 0.0;
f>>n;
for(i=0; i<n; i++) {
f>>a>>b;
temp.x = a;
temp.y = b;
p.push_back(make_pair(0.0, temp));
}
source = p[0].coord;
for(i=1; i<p.size(); i++) {
if(p[i].coord.y < source.y) source = p[i].coord;
else if(p[i].coord.y == source.y && p[i].coord.x < source.x) source = p[i].coord;
}
for(i=0; i<n; i++) {
if(p[i].coord.x == source.x && p[i].coord.y == source.y) polar_angle = -5.0; //it's the source, so it stays first after sorting
else polar_angle = atan2( p[i].coord.y-source.y, p[i].coord.x-source.x );
p[i].angle = polar_angle;
}
sort(p.begin(), p.end(), cmp);
//for(i=0; i<p.size(); i++) g<<p[i].coord.x<<" "<<p[i].coord.y<<": "<<p[i].angle<<"\n";
S.push_back(p[0].coord);
S.push_back(p[1].coord);
S.push_back(p[2].coord);
for(i=3; i<p.size(); i++) {
while( ccw(top(S), next_to_top(S), p[i].coord) >= 0 ) S.pop_back();
S.push_back(p[i].coord);
}
g<<S.size()<<"\n";
g<<fixed;
g<<setprecision(5);
for(i=0; i<S.size(); i++) {
g<<S[i].x<<" "<<S[i].y<<"\n";
}
return 0;
}