Pagini recente » Cod sursa (job #854416) | Cod sursa (job #368138) | Cod sursa (job #153266) | Cod sursa (job #2514058) | Cod sursa (job #2158203)
#include <bits/stdc++.h>
using namespace std;
int const INF=2e9;
int const NMAX=120000;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct POINT{
double x, y;
}p[NMAX+20], LL, pct, stiva[NMAX+20];
int ls;
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==0) return 0;
return -1;
}
bool cmp(POINT a, POINT b){
int c=ccw(LL, a, b);
if (c==1) return true;
if (c==0) return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
return false;
}
int main(){
int i, n;
in >> n;
LL={INF, INF};
for (int i=0; i<=n-1; i++){
in >> pct.x >> pct.y;
if (LL.y>pct.y){
p[i]=LL;
LL=pct;
}
else if (LL.y==pct.y && LL.x>pct.y){
p[i]=LL;
LL=pct;
}
else p[i]=pct;
}
sort(p+1, p+n, cmp);
p[n]=LL;
stiva[1]=LL;
stiva[2]=p[1];
ls=2;
for (i=2; i<=n; i++){
while (ls>=2 && ccw(stiva[ls-1], stiva[ls], p[i])==-1) ls--;
stiva[++ls]=p[i];
}
out << ls-1 << '\n';
for (i=1; i<=ls-1; i++)
out << stiva[i].x << ' ' << stiva[i].y << '\n';
}