Cod sursa(job #1497696)

Utilizator Burbon13Burbon13 Burbon13 Data 7 octombrie 2015 10:08:07
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define s second
#define f first
#define pub push_back
#define pob pop_back
using namespace std;

const int nmx = 120002;

int n;
pair <double,double> p[nmx];
vector <int> sus,jos;

int determinant(int p1, int p2, int p3) {
    return (((p[p2].f-p[p1].f)*(p[p3].s-p[p1].s))-((p[p3].f-p[p1].f)*(p[p2].s-p[p1].s))) >= 0 ? 1 : -1;
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &p[i].f, &p[i].s);

    sort(p+1,p+n+1);

    sus.pub(1);
    sus.pub(2);
    jos.pub(1);
    jos.pub(2);

    int s = 2, j = 2;
    for(int i = 3; i <= n; ++i) {
        while(s >= 2 && determinant(sus[s-2],sus[s-1],i) == 1) {
            sus.pob();
            -- s;
        }
        sus.pub(i);
        ++ s;
        while(j >= 2 && determinant(jos[j-2],jos[j-1],i) == -1) {
            jos.pob();
            -- j;
        }
        jos.pub(i);
        ++ j;
    }

    int sum = s + j;

    if(jos[0] == sus[0]) {
        -- sum;
        jos[0] = -1;
    }
    if(jos[j-1] == sus[s-1]) {
        -- sum;
        sus[s-1] = -1;
    }

    printf("%d\n", sum);

    for(int i = 0; i < j; ++i)
        if(jos[i] >= 0)
            printf("%lf %lf\n", p[jos[i]].f, p[jos[i]].s);
    for(int i = s - 1; i >= 0 ; --i)
        if(i >= 0 && sus[i] >= 0)
            printf("%lf %lf\n", p[sus[i]].f, p[sus[i]].s);

    return 0;
}