Cod sursa(job #2019713)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 8 septembrie 2017 13:06:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX=120005;
const double eps=1.0e-14;
struct POINT{
    double x,y;
}p[NMAX];
int h[NMAX];
double dist(POINT p1, POINT p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double CrossProduct(POINT a, POINT b, POINT c){
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int CounterClockWise(POINT a, POINT b, POINT c){
    double cp=CrossProduct(a, b, c);
    if(fabs(cp)<eps)
        return 0;
    if(cp>=eps)
        return 1;
    return -1;
}
bool cmp(POINT p1, POINT p2){
    int c=CounterClockWise(p[0], p1, p2);
    if(c==1)
        return 1;
    if(c==-1)
        return 0;
    double d1=dist(p[0], p1);
    double d2=dist(p[0], p2);
    if(d1-d2<=eps)
        return 1;
    return 0;
}
int main(){
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int top,n,ll=-1;
    double minx=1000000005,miny=1000000005;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(miny-p[i].y>=eps){
            minx=p[i].x;
            miny=p[i].y;
            ll=i;
        }
        else
            if(fabs(p[i].y-miny)<eps && minx-p[i].x>=eps){
                ll=i;
                minx=p[i].x;
            }
    }
    p[0]=p[ll];
    sort(p+1, p+n, cmp);
    p[n]=p[0];
    h[1]=top=1;
    int i=2;
    while(i<=n)
        if(CounterClockWise(p[h[top-1]], p[h[top]], p[i])>0){
            h[++top]=i;
            i++;
        }
        else
            top--;
    printf("%d\n", top);
    for(int i=0;i<top;i++)
        printf("%f %f\n", p[h[i]].x, p[h[i]].y);
    return 0;
}