Pagini recente » Cod sursa (job #509602) | Cod sursa (job #2755791) | Cod sursa (job #2569364) | Cod sursa (job #2503615) | Cod sursa (job #3226991)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
double x, y;
}a[130005];
int n;
double getWay(Point A, Point B, Point C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
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[130005];
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;
}