Pagini recente » Cod sursa (job #2068157) | Monitorul de evaluare | Cod sursa (job #2456746) | Istoria paginii runda/oji2008x/clasament | Cod sursa (job #3195979)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <stack>
#include <iomanip>
using namespace std;
#define F long double
const F eps = 1e-12;
ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.out");
bool isright(F x1, F y1, F x2, F y2, F x3, F y3)
{
F s = (-(x3-x2))*((y2-y1))/((x1-x2));
return ((s + y2 - y3) >= 0) ^ ((x1 - x2) >= 0);
}
F isRight(F x1, F y1, F x2, F y2, F x3, F y3)
{
return ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
}
F dsq(F x1, F y1, F x2, F y2)
{
return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
struct c {F x; F y;
bool operator<(const struct c &other) const
{
if(y == other.y)
return x<other.x;
return y<other.y;
}
};
F angle(c f, c s)
{
return atan2(s.y-f.y, s.x-f.x);
}
bool iscolinear(c f, c s, c t)
{
F g = (-(t.x-s.x))*((s.y-f.y))/((f.x-s.x));
return abs(g + s.y - t.y) <= eps;
}
F cisright(c f, c s, c t)
{
return (isRight(f.x, f.y, s.x, s.y, t.x, t.y));
}
template<typename T>
T peek(stack<T>& s)
{
const T x = s.top();
s.pop();
const T y = s.top();
s.push(x);
return y;
}
void print(stack<c> s)
{
while(!s.empty())
{
fout << s.top().x << " " << s.top().y << endl;
s.pop();
}
}
stack<c> convexhullr(vector<c> p)
{
stack<c> s;
s.push(p[0]);
s.push(p[1]);
for(int i=2; i<p.size(); i++) {
while(s.size() >= 2 && cisright(peek(s), s.top(), p[i]) < 0)
s.pop();
s.push(p[i]);
}
return s;
}
stack<c> convexhulll(vector<c> p)
{
stack<c> s;
s.push(p[0]);
s.push(p[1]);
for(int i=2; i<p.size(); i++) {
while(s.size() >= 2 && cisright(peek(s), s.top(), p[i]) > 0)
s.pop();
s.push(p[i]);
}
return s;
}
stack<c> rev(stack<c> a)
{
stack<c> b;
while(!a.empty())
{
b.push(a.top());
a.pop();
}
return b;
}
int main()
{
int k;
fout << fixed;
fout << setprecision(0);
vector<c> a;
fin >> k;
for(int i=0; i<k; i++)
{
F x, y;
fin >> x >> y;
a.push_back((struct c){x,y});
}
sort(a.begin(), a.end());
stack<c> s1 = rev(convexhullr(a));
stack<c> s2 = convexhulll(a);
s2.pop();
s2=rev(s2);
s2.pop();
s2=rev(s2);
fout << s1.size()+s2.size() << endl;
print(s1);
print(s2);
return 0;
}