Pagini recente » Cod sursa (job #369103) | Cod sursa (job #3218434) | Cod sursa (job #533555) | Cod sursa (job #1020894) | Cod sursa (job #2936401)
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
using namespace std;
struct Punct{
long double x, y; }p, Start;
void Graham_scan(vector<Punct>&v, vector<Punct>&sol);
int orientare(Punct a, Punct b, Punct c);
bool comparator(Punct a, Punct b);
void input(vector<Punct>&v);
void output(vector<Punct>sol);
vector<Punct> v, sol;
fstream f, g;
int n;
int main()
{
input(v);
Graham_scan(v, sol);
output(sol);
return 0;
}
void Graham_scan(vector<Punct>&v, vector<Punct>&sol){
Punct Start = v[0];
int i, dim = v.size()-1;
for( i = 1; i < v.size(); ++i)
if( v[i].y < Start.y or v[i].y == Start.y and v[i].x < Start.x)
Start = v[i];
///pana aici am gasit punctul din stanga jos minim
sort(v.begin(), v.end(), comparator);
while( dim >= 0 and orientare(Start, v[dim], v.back()) == 1 )
--dim;
reverse( v.begin()+dim+1, v.end() );
Punct A, B, C;
for( i = 0; i < v.size(); ++i )
{
while( sol.size() > 1 )
{
A = sol[ sol.size() - 2];
B = sol.back();
C = v[i];
int arie = orientare(A, B, C);
if(arie > 0) sol.pop_back();
else break;
}
sol.push_back( v[i] );
}
}
void input(vector<Punct>&v){
ios::sync_with_stdio(false);
f.open(IN, ios::in);
g.open(OUT, ios::out);
f >> n;
g << fixed << setprecision(6);
for(int i = 0; i < n; i++){
f >> p.x >> p.y;
v.push_back(p);
}
f.close();
}
void output(vector<Punct>sol){
g << sol.size() << '\n';
for(int i = sol.size()-1; i >= 0; --i)
g << sol[i].x <<' '<<sol[i].y<<'\n';
g.close();
}
int orientare(Punct A, Punct B, Punct C){
long double panta = A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
if( panta > 0 ) return 1;
else if( !panta ) return 0;
return -1;
}
bool comparator(Punct A, Punct B){
int arie = orientare(Start, A, B);
if( !arie )
{
long double d_Start_A_patrat = (A.x - Start.x)*(A.x - Start.x) + (A.y - Start.y)*(A.y - Start.y);///folsoesc dezvoltarea Gauss-Jacobi
long double d_Start_B_patrat = (B.x - Start.x)*(B.x - Start.x) + (B.y - Start.y)*(B.y - Start.y);///de asemenea pot folosi si raportul pantelor
if( A.y == B.y ) return(d_Start_A_patrat > d_Start_B_patrat);
return (d_Start_A_patrat < d_Start_B_patrat);
}
return arie < 0;
}