Pagini recente » Cod sursa (job #937211) | Cod sursa (job #1533360) | Cod sursa (job #1572890) | Cod sursa (job #2108018) | Cod sursa (job #3222221)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x, y;
};
const int mxN = 120001;
int n, k;
point pts[mxN], ans[mxN];
void readInput()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> pts[i].x >> pts[i].y;
}
}
double orientation(point A, point B, point C)
{
/*
two lines: AB and BC
mAB = (yB - yA) / (xB - xA)
mBC = (yC - yB) / (xC - xB)
mAB == mBC => collinear 0
mBC > mAB => counterclockwise (ccw) +
mBC < mAB => clockwise (cw) -
*/
return (C.y - B.y) * (B.x - A.x) - (C.x - B.x) * (B.y - A.y);
}
bool compare(point A, point B)
{
// should return true if 'A < B'
if (orientation(pts[1], A, B) > 0)
{
return true;
}
return false;
}
void ccwSort()
{
int idx = 1;
for (int i = 2; i <= n; i++)
{
if (pts[i].y < pts[idx].y || pts[i].y == pts[idx].y && pts[i].x < pts[idx].x)
{
idx = i;
}
}
swap(pts[1], pts[idx]);
sort(pts + 2, pts + n + 1, compare);
/*
for (int i = 2; i <= n; i++)
{
double tan = (pts[i].y - pts[1].y) / (pts[i].x - pts[1].x);
cout << tan << "\n";
}
*/
}
void convexHull()
{
ans[++k] = pts[1];
ans[++k] = pts[2];
for (int i = 3; i <= n; i++)
{
while (k >= 2 && orientation(ans[k - 1], ans[k], pts[i]) < 0)
{ // as long as they are cw, the last one is problematic
k--;
}
ans[++k] = pts[i];
}
}
void displayAnswer()
{
fout << k << "\n";
for (int i = 1; i <= k; i++)
{
fout << ans[i].x << " " << ans[i].y << "\n";
}
}
int main()
{
readInput();
ccwSort();
convexHull();
displayAnswer();
return 0;
}