Pagini recente » Cod sursa (job #464461) | Cod sursa (job #2184499) | Cod sursa (job #1380100) | Cod sursa (job #638022) | Cod sursa (job #803323)
Cod sursa(job #803323)
// InfasuratoareConvexa.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
typedef struct
{
long double x,y;
} punct;
unsigned int n;
std::vector<punct> m_nPoints;
std::vector<punct> m_upperPoints;
std::vector<punct> m_lowerPoints;
bool cmp(punct a, punct b)
{
if(a.x < b.x)
return true;
if(a.x == b.x)
if(a.y < b.y)
return true;
return false;
}
void read()
{
FILE *f;
fopen("infasuratoare.in", "r");
fscanf(f, "%u", &n);
for(unsigned i = 0; i < n; i++)
{
punct x;
fscanf(f, "%Lf%Lf", &x.x, &x.y);
m_nPoints.push_back(x);
}
fclose(f);
}
long double determinant(punct a, punct b, punct c) //pozitia lui c fata de ab
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void calculateUpperLowerPoints()
{
sort(m_nPoints.begin(), m_nPoints.end(), cmp);
punct p1 = *m_nPoints.begin(), pmax = *(m_nPoints.end() - 1);
m_lowerPoints.push_back(p1);
m_upperPoints.push_back(p1);
for(std::vector<punct>::iterator it = m_nPoints.begin() + 1; it != m_nPoints.end() - 1; it++)
{
if(determinant(p1, pmax, *it) > 0)
m_upperPoints.push_back(*it);
else
m_lowerPoints.push_back(*it);
}
m_lowerPoints.push_back(pmax);
m_upperPoints.push_back(pmax);
}
void solve()
{
std::stack<punct> upperStack;
std::stack<punct> lowerStack;
FILE *g;
fopen("infasuratoare.out", "w");
upperStack.push(m_upperPoints[0]);
upperStack.push(m_upperPoints[1]);
for(int i = 2; i < m_upperPoints.size(); i++)
{
punct a = m_upperPoints[i];
punct x = upperStack.top();
upperStack.pop();
while(upperStack.empty() == false && determinant(upperStack.top(), a, x) < 0)
{
x = upperStack.top();
upperStack.pop();
}
upperStack.push(x);
upperStack.push(a);
}
lowerStack.push(m_lowerPoints[0]);
lowerStack.push(m_lowerPoints[1]);
for(int i = 2; i < m_lowerPoints.size(); i++)
{
punct a = m_lowerPoints[i];
punct x = lowerStack.top();
lowerStack.pop();
while(lowerStack.empty() == false && determinant(lowerStack.top(), a, x) > 0)
{
x = lowerStack.top();
lowerStack.pop();
}
lowerStack.push(x);
lowerStack.push(a);
}
fprintf(g, "%d\n", lowerStack.size() + upperStack.size() - 2);
unsigned k = lowerStack.size();
m_lowerPoints.clear();
for(int i = 0; i < k - 1; i++)
{
m_lowerPoints.push_back(lowerStack.top());
lowerStack.pop();
}
for(int i = m_lowerPoints.size() - 1; i >= 0; i--)
fprintf(g, "%Lf %Lf\n", m_lowerPoints[i].x, m_lowerPoints[i].y);
upperStack.pop();
while(upperStack.empty() == false)
{
fprintf(g, "%Lf %Lf\n", upperStack.top().x, upperStack.top().y);
upperStack.pop();
}
fclose(g);
}
int main(int argc, char* argv[])
{
read();
calculateUpperLowerPoints();
solve();
return 0;
}