Cod sursa(job #3247493)

Utilizator comanandreiComan Andrei comanandrei Data 8 octombrie 2024 00:17:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <stdio.h>
#include <algorithm>

#define MAXN 120000

using namespace std;

struct point{
    double x, y;
};

point puncte[MAXN];
point my_stack_left[MAXN+1], my_stack_right[MAXN+1];
int stack_pointer_left, stack_pointer_right;

bool cmp(const point&a, const point &b){
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}

bool AreaIsPositive(point a, point b, point c){
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y>0;
}

void my_push_back(point p, bool stanga){
    if(stanga)
        my_stack_left[++stack_pointer_left]=p;
    else
        my_stack_right[++stack_pointer_right]=p;
}

void my_pop(bool stanga){
    if(stanga)
        stack_pointer_left--;
    else
        stack_pointer_right--;
}

int my_size(bool stanga){
    if(stanga)
        return stack_pointer_left;
    else
        return stack_pointer_right;
}

int main()
{
    FILE *fin, *fout;
    int n, i;
    fin=fopen("infasuratoare.in", "r");
    fscanf(fin, "%d", &n);
    for(i=0;i<n;i++){
        fscanf(fin, "%lf%lf", &puncte[i].x, &puncte[i].y);
    }
    fclose(fin);
    sort(puncte, puncte+n, cmp);
    my_push_back(puncte[0], 0);
    my_push_back(puncte[0], 1);
    stack_pointer_left=stack_pointer_right=1;
    for(i=1;i<n-1;i++){
        ///stanga==1
        if(AreaIsPositive(puncte[0], puncte[n-1], puncte[i])){///lucrez cu stiva din stanga
            while(my_size(1)>1&&AreaIsPositive(my_stack_left[stack_pointer_left-1], my_stack_left[stack_pointer_left], puncte[i])){
                my_pop(1);
            }
            my_push_back(puncte[i], 1);
        }
        else{///lucrez cu stiva din dreapta
            while(my_size(0)>1&&!AreaIsPositive(my_stack_right[stack_pointer_right-1], my_stack_right[stack_pointer_right], puncte[i])){
                my_pop(0);
            }
            my_push_back(puncte[i], 0);
        }
    }
    ///verific daca nu cumva mai trebuie sa scot puncte datorita celui mai de sus punct
    while(my_size(1)>1&&AreaIsPositive(my_stack_left[stack_pointer_left-1], my_stack_left[stack_pointer_left], puncte[n-1])){
        my_pop(1);
    }
    while(my_size(0)>1&&!AreaIsPositive(my_stack_right[stack_pointer_right-1], my_stack_right[stack_pointer_right], puncte[n-1])){
        my_pop(0);
    }
    fout=fopen("infasuratoare.out", "w");
    fprintf(fout, "%d\n", stack_pointer_left+stack_pointer_right);
    for(i=1;i<=stack_pointer_right;i++){
        fprintf(fout, "%.12lf %.12lf\n", my_stack_right[i].x, my_stack_right[i].y);
    }
    fprintf(fout, "%.12lf %.12lf\n", puncte[n-1].x, puncte[n-1].y);
    for(i=stack_pointer_left;i>1;i--){
        fprintf(fout, "%.12lf %.12lf\n", my_stack_left[i].x, my_stack_left[i].y);
    }
    fclose(fout);
    return 0;
}