Pagini recente » Cod sursa (job #3212430) | Cod sursa (job #576984) | Cod sursa (job #1680795) | Cod sursa (job #3120447) | Cod sursa (job #2084068)
#include <bits/stdc++.h>
using namespace std;
int const INF = 2e9;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct POINT{
double x, y;
}p[120001], pct, stiva[120001];
POINT BL={INF, INF};
int ls=0;
int ccw(POINT a, POINT b, POINT c){
int cp=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if (cp>0) return 1;
else if (!cp) return 0;
return -1;
}
bool cmp(POINT a, POINT b){
int c=ccw(BL, a, b);
if (c==0) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
if (c==1) return true;
else return false;
}
int main(){
int i, n;
in >> n;
for (int i=0; i<=n-1; i++){
in >> pct.x >> pct.y;
if (BL.x>pct.x && BL.y>pct.y){
p[i]={BL.x, BL.y};
BL={pct.x, pct.y};
}
else p[i]={pct.x, pct.y};
}
sort(p+1, p+n, cmp);
p[n]={BL.x, BL.y};
stiva[1]=p[1];
stiva[2]=p[2];
ls=2;
for (i=3; i<=n; i++){
while (ccw(stiva[ls-2], stiva[ls-1], p[i])==1) ls--;
stiva[++ls]={p[i].x, p[i].y};
}
out << ls << '\n';
for (i=1; i<=ls; i++)
out << stiva[i].x << ' ' << stiva[i].y << '\n';
}