Pagini recente » Cod sursa (job #2774242) | Cod sursa (job #100214) | Cod sursa (job #2840288) | Cod sursa (job #686561) | Cod sursa (job #653422)
Cod sursa(job #653422)
/*
* File: Infasuratoareconvexa.cpp
* Author: slycer
*
* Created on December 25, 2011, 7:49 PM
*/
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
class Punct {
public:
double x, y;
Punct(double x, double y) {
this->x = x;
this->y = y;
}
void print(){
cout << x << " " << y ;
}
double slope( Punct &punct ){
if ( x - punct.x != 0 ){
return ( y - punct.y)/( x - punct.x );
} else {
return abs( y - punct.y );
}
}
};
double angle( Punct base, Punct r ){
double a = r.x - base.x;
double b = r.y - base.y;
return atan2(a,b);
}
double area( Punct a, Punct b, Punct c ){
return ( a.x - c.x ) * ( b.y - a.y ) - ( a.x - b.x ) * ( c.y - a.y );
}
Punct minim(0,0);
double distanta( Punct a, Punct b ){
double unu = (a.x-b.x);
double doi = (a.y - b.y );
return unu * unu + doi * doi;
}
bool angular_sort( Punct a, Punct b )
{
double unu = angle( minim, a );
double doi = angle( minim, b );
if ( unu == doi ){
return distanta( minim, a ) < distanta( minim, b );
} else {
return unu > doi;
}
}
/*
*
*/
int main(int argc, char** argv) {
ifstream input("infasuratoare.in");
ofstream output("infasuratoare.out");
vector<Punct> puncte;
int n;
input >> n;
for ( int i=0; i<n; i++ ){
double x,y;
input >> x >> y;
puncte.push_back( Punct(x,y) );
}
minim = Punct( puncte[0].x, puncte[0].y );
for ( int i=1; i<n; i++ ){
if ( minim.x > puncte[i].x || ( minim.x == puncte[i].x && minim.y > puncte[i].y ) ){
minim = puncte[i];
}
}
//minim.print();
sort( puncte.begin(), puncte.end(), angular_sort );
//for ( int i=0; i<puncte.size(); i++ ){
// cout << "\n";
// puncte[i].print();
// cout << " " << angle( minim, puncte[i] ) << "\n" ;
//}
vector<Punct> stack;
stack.push_back( minim );
for ( int i=0; i<puncte.size(); i++ ){
if ( puncte[i].x == minim.x && puncte[i].y == minim.y ){
} else {
while ( true ){
if ( stack.size() <= 2 ){
stack.push_back( puncte[i] );
break;
} else {
int s = stack.size();
if ( area(stack[s-2], stack[s-1], puncte[i] ) >= 0 ){
stack.push_back( puncte[i] );
break;
} else {
stack.pop_back();
}
}
}
}
}
output.precision( 16 );
output << stack.size() << "\n";
for ( int i=0; i<stack.size(); i++){
output << stack[i].x << " " << stack[i].y << "\n";
}
return 0;
}