Cod sursa(job #2080896)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 3 decembrie 2017 16:55:54
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1.e-14;
struct point{
double x,y;
};
point ll;
double cp(point p1,point p2,point p3)
{
    return (p3.x-p1.x)*(p3.y-p2.y)
    - (p3.y - p1.y) * (p3.x - p2.x );
}
int ccw(point p1,point p2,point p3)
{
    double c =cp(p1,p2,p3);
    if(fabs(c)<eps)
        return 0;
    if(c > eps)
        return 1;
    return -1;
}
double dist (point p1 , point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x- p2.x) + (p1.y-p2.y)*(p1.y- p2.y));
}

vector <point>v;
int st[120001];
bool cmp(point a,point b)
{
  return ccw(v[0], a, b) > ccw(v[0], b, a);
}
int main(){
    int n,i,poz,top;
    double x,y;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    ll.x=1000000005;
    ll.y=1000000005;
    for(i = 1; i <= n ; i ++)
    {
        scanf("%lf%lf",&x,&y);
        v.push_back({x,y});
        if(ll.y - y >= eps){
            ll.y = y;
            ll.x = x;
            poz=i;
        }
        else if(fabs(ll.y - y) <= eps)
            if(ll.x - x >= eps)
            {
                ll.y = y;
                ll.x = x;
                poz=i;
            }
    }
    swap(v[0],v[poz]);
    sort(v.begin() + 1, v.begin() + n, cmp);
    st[0] = 0;
  st[1] = 1;
   top = 1;
  v[n] = v[0];
  for (int i = 2; i <= n; ++i){
    while (top > 1 && ccw(v[st[top]], v[st[top - 1]], v[i]) != ccw(v[st[top]], v[st[top - 1]], v[st[top - 2]]))
      top--;
    st[++top] = i;
  }
    printf("%d\n",top);
    for(i = 0; i < top ;i ++)
      printf("%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
    return 0;
}