Pagini recente » Cod sursa (job #2159425) | Cod sursa (job #1106974) | Cod sursa (job #2750031) | Cod sursa (job #287874) | Cod sursa (job #1581315)
//algoritmi sunt implementati bazandu-ma pe pseudocodul de aici http://gta.math.unibuc.ro/stup/geom_comp.pdf
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <deque>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
#define foreach(i,n) for(int i = 0; i < n ; i++)
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const long double epsilon = 10e-15;
//algoritmul lent infasuratoare convexa O(n^4)c
struct Point
{
long double x,y,pa,pd;
Point(){x = 0; y = 0; pa= 0; pd = 0;}
Point(long double xx,long double yy){ x = xx; y = yy; pa= 0 ; pd= 0 ;}
friend istream& operator >>( istream& i , Point& p );
friend ostream& operator <<( ostream& o, Point&p );
friend ostream& operator<<( ostream&o, const Point& p );
bool operator != ( const Point& B );
bool operator != ( const Point& B )const;
bool operator ==( const Point&B )const;
Point operator /=( long double divide );
Point operator +=( const Point& );
};
bool orientation( Point p0,Point p1, Point p2)
{
Point p1prim,p2prim;
p1prim.x = p1.x - p0.x;
p1prim.y = p1.y - p0.y;
p2prim.x = p2.x - p0.x;
p2prim.y = p2.y - p0.y;
return (p1prim.x * p2prim.y - p2prim.x * p1prim.y >= 0);//p1 in dreapta lu p2
}
Point Point::operator +=(const Point& B)
{
x += B.x;
y += B.y;
return *this;
}
Point Point::operator /=(long double divide)
{
x /= divide;
y /= divide;
return *this;
}
bool Point::operator !=(const Point& B)
{
if (x == B.x && y == B.y)
return false;
return true;
}
bool Point::operator ==(const Point&B)const
{
if( x == B.x && y == B.y)
return true;
return false;
}
bool Point::operator !=(const Point& B)const
{
if (x == B.x && y == B.y)
return false;
return true;
}
istream& operator>>(istream& i , Point& p)
{
i >> p.x >> p.y;
return i;
}
ostream& operator<<(ostream& o , Point&p)
{
o<< fixed << setprecision(2) << p.x<< " "<< fixed << setprecision(2) <<p.y;
return o;
}
ostream& operator<<(ostream&o,const Point& p)
{
o<<fixed<<setprecision(6)<<p.x<<" "<<fixed<<setprecision(6)<<p.y<<'\n';
return o;
}
void Grahams_Scan_Convex_Hull(vector<Point>&P2)
//O(nlogn) here is a good example+pseudocod https://www.youtube.com/watch?v=QYrpHE8iDGg
//also we can test here https://www.mathsisfun.com/data/cartesian-coordinates-interactive.html
{
//sortam punctele
Point p0(1000000000,1000000000);
stack<Point> s;
for( auto &p:P2)
if(p.y<p0.y)
p0 = p;
else
if(p.y == p0.y)
if( p.x < p0.x)
p0 = p;
vector<Point>P;
for(auto it = P2.begin() ; it!=P2.end() ; it++)
if ( *it != p0)
{
P.push_back(*it);
}
sort(P.begin(),P.end(),[=](Point a,Point b)->bool{ return orientation(p0,a,b);});
auto it = P.begin();
s.push(p0);
s.push(*it);
s.push(*(it+1));
Point p1,p2,pi;
for(auto p = it+3; p!=P.end() ; p++)
{
pi = *p;
p2 = s.top();
s.pop();
p1 = s.top();
s.push(p2);
while( !orientation(p1,p2,pi))
{
s.pop();
p2 = p1;
s.pop();
p1 = s.top();
s.push(p2);
}
s.push(pi);
}
deque<Point> dP;
while(!s.empty())
{
dP.push_front(s.top());
s.pop();
}
out<<dP.size()<<'\n';
for(const auto& it:dP)
out<<it;
}
int main()
{
int n;
in>>n;
Point p;
vector<Point> P;
foreach(i,n)
{
in>>p;
P.push_back(p);
}
Grahams_Scan_Convex_Hull(P);
return 0;
}