Pagini recente » Cod sursa (job #342986) | Cod sursa (job #403174) | Cod sursa (job #1338834) | Cod sursa (job #2679850) | Cod sursa (job #3226986)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
double x, y;
}a[100005];
int n;
double getWay(Point A, Point B, Point C)
{
double xAB, yAC, xAC, yAB;
xAB = B.x - A.x;
yAB = B.y - A.y;
xAC = C.x - A.x;
yAC = C.y - A.y;
return 1LL * xAB * yAC - 1LL * yAB * xAC;
}
bool cmp(Point A, Point B)
{
return getWay(a[0], A, B) < 0;
}
void Citire()
{
fin >> n;
for(int i = 1;i <= n;i++)
fin >> a[i].x >> a[i].y;
int minP = -1;
double minim = 1e9;
for(int i = 1;i <= n;i++)
if(minim > a[i].y){
minim = a[i].y;
minP = i;
}
swap(a[1], a[minP]);
sort(a + 1, a + n + 1, cmp);
}
int stv[100005];
void ConvexHull()
{
int top = 0;
stv[++top] = 1;
stv[++top] = 2;
for(int i = 3;i <= n;i++){
while(top >= 2 && getWay(a[stv[top - 1]], a[stv[top]], a[i]) >= 0)
top--;
stv[++top] = i;
}
fout << top << "\n";
while(top){
fout << setprecision(9) << fixed << a[stv[top]].x << " " << a[stv[top]].y << "\n";
top--;
}
}
int main() {
Citire();
ConvexHull();
return 0;
}