Pagini recente » Cod sursa (job #677770) | Cod sursa (job #3300869) | Cod sursa (job #634078) | Cod sursa (job #683335) | Cod sursa (job #3300872)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define MAX 1000000000.0
typedef struct
{
float x, y, angle;
} POINT;
vector<POINT> points;
POINT origin = {MAX, MAX, 0.0};
void printPoint(POINT point)
{
fout << point.x << ' ' << point.y << '\n';
}
float computeAngle(POINT point, POINT origin)
{
return atan2(point.y - origin.y, point.x - origin.x);
}
bool compareFunction(POINT a, POINT b)
{
if (a.angle == b.angle)
{
float distA = (a.x - origin.x) * (a.x - origin.x) + (a.y - origin.y) * (a.y - origin.y);
float distB = (b.x - origin.x) * (b.x - origin.x) + (b.y - origin.y) * (b.y - origin.y);
return (distA > distB);
}
return (a.angle < b.angle);
}
bool isConvex(POINT prev, POINT current, POINT next)
{
float product = (current.x - prev.x) * (next.y - prev.y) - (current.y - prev.y) * (next.x - prev.x);
return (product > 0);
}
void processInput()
{
int n;
fin >> n;
points.resize(n);
for (int i = 0; i < n; i++)
{
float X, Y;
fin >> X >> Y;
points[i] = {X, Y, 0.0};
if (points[i].y < origin.y)
{
origin = points[i];
}
else if (points[i].y == origin.y)
{
if (points[i].x < origin.x)
{
origin = points[i];
}
}
}
for (int i = 0; i < n; i++)
{
points[i].angle = computeAngle(points[i], origin);
}
sort(points.begin(), points.end(), compareFunction);
int j = 0;
for (long unsigned int i = 1; i < points.size(); i++)
{
if (fabs(points[i].angle - points[j].angle) != 0)
{
points[++j] = points[i];
}
}
points.resize(j + 1);
}
void printResult(vector<POINT>& st)
{
fout << st.size() << '\n';
for (long unsigned int i = 0; i < st.size(); i++)
{
printPoint(st[i]);
}
}
void solve()
{
vector<POINT> st;
st.push_back(points[0]);
if (points.size() > 1)
{
st.push_back(points[1]);
}
for (long unsigned int i = 2; i < points.size(); i++)
{
while (st.size() >= 2)
{
POINT current = st[st.size() - 1];
POINT prev = st[st.size() - 2];
POINT next = points[i];
if (!isConvex(prev, current, next))
{
st.pop_back();
}
else
{
break;
}
}
st.push_back(points[i]);
}
printResult(st);
}
int main()
{
processInput();
solve();
return 0;
}