Fie A o mulțime de N puncte Ai în plan de coordonate întregi cunoscute (Ai.x, Ai.y). Pentru o întrebare definită printr-un punct Q=(Q.x, Q.y) se cere aria înfășurătorii convexe a punctelor: {Q} ∪ {Ai | Ai.x < Q.x și Ai ∈ A }.

Înfășurătoarea convexă a unei mulțimi de puncte este poligonul convex de arie minimă care conține toate punctele în interior sau pe laturile acestuia.

Cerinţă

Determinați răspunsurile pentru M întrebări de tipul enunţat mai sus, relativ la mulțimea inițială A.

Date de intrare

Pe prima linie a fişierului geometrie.in se află numerele naturale nenule N și M.
Următoarele N linii conțin câte două numere Ai.x Ai.y separate printr-un spațiu.
Următoarele M linii conțin câte două numere Q.x Q.y separate printr-un spațiu.
În fișierul de intrare atât punctele Ai cât și punctele Q sunt în ordinea crescătoare a valorilor x.

Date de ieşire

În fişierul geometrie.out vor fi M linii care conțin răspunsurile la întrebări, în ordinea în care au fost cerute, fiecare pe câte o linie. Afişaţi fiecare număr cu o zecimală precizie.

Restricţii şi precizări

N, M ≤ 10^5
Toate coordonatele Ai.x, Ai.y, Qx și Qy ≤ 10^9
Punctele din mulțimea A au valori Xi distincte.
Înfășurătoarea convexă a unei mulțimi cu cel mult două puncte are aria egală cu zero.
Pentru teste în valoare de 20 puncte N ≤ 3
Pentru teste în valoare de 40 puncte N×M ≤ 10^3
Pentru teste în valoare de 60 puncte N×M ≤ 10^6

Exemplul 1

geometrie.in

geometrie.out

0.0
15.0
14.5

Exemplul 2

geometrie.in

geometrie.out

3.0
32.0

Explicație

Poligoanele formate din punctele care se obțin pentru cele doua întrebări de la exemplul 2 sunt:

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Geometrie:

/*
Time complexity: O(M * log N), ~100 points
Paul Diac
*/
#include <stdio.h>
#include <stdlib.h>
#define NMax 100000
#define MMax 100000
#define llong long long

FILE *fin = fopen("geometrie.in", "rt");
FILE *fout = fopen("geometrie.out", "wt");

typedef struct point {
    int x, y;
} point;

int N, M;
point a[NMax], q[NMax];

long long area(point a, point b, point c) {
    return (llong) a.x * b.y + (llong) a.y * c.x + (llong) b.x * c.y
         - (llong) a.x * c.y - (llong) a.y * b.x - (llong) b.y * c.x; }

long long areaTrap(point a, point b) { // 'below' trapezoid area, doubled, a.x < b.x
    return (llong) (b.x - a.x) * (a.y + b.y);
}

typedef struct stack {
    point p[NMax];
    llong aLeft[NMax]; // area on left side, below
    int top;
} stack;

stack up, dn; // up and down stack

int getTangent(stack &st, point q, int sgn) {
    int pi = st.top, step;
    for (step = 1; step < pi; step <<= 1);
    for (; step; step>>=1) {
        if (pi-step-1 >= 0 && area(q, st.p[pi-step], st.p[pi-step-1]) * sgn < 0) {
            pi -= step;
        }
    }
    for (; pi > 0 && area(q, st.p[pi], st.p[pi-1]) * sgn < 0; pi--);
    return pi;  
}

llong solveQuery(point q) { // stacks must have CH points with x < q.xlim

    if (up.top == 0) {
        return 0;
    }

    int upi = getTangent(up, q, 1);
    int dni = getTangent(dn, q, -1);

    llong rez = 0;
    rez += up.aLeft[upi];
    rez -= dn.aLeft[dni];
    rez += areaTrap(up.p[upi], q);
    rez -= areaTrap(dn.p[dni], q);
    return rez;
}

void addPointToStack(stack &st, point p, int sign) {
    for (; st.top > 0 && area(p, st.p[st.top], st.p[st.top-1]) * sign < 0; st.top--);
    // no need to bsearch here, amortized complexity is linear
    st.aLeft[st.top+1] = st.aLeft[st.top] + areaTrap(st.p[st.top], p);
    st.p[++st.top] = p;
}

void solve() {

    up.p[0] = a[0];
    dn.p[0] = a[0];
    int ai = 0, qi = 0; // A[] set and query idx

    for (ai = 1; ai < N || qi < M; ai++) {

        // answers queries with q[i].x <= a[ai].x
        for (; qi < M && q[qi].x <= a[ai].x; qi++) {
            fprintf(fout, "%.1lf\n", (double) solveQuery(q[qi]) / 2);
        }

        if (ai < N) {
            // add point a[ai] to stacks
            addPointToStack(up, a[ai], 1);
            addPointToStack(dn, a[ai], -1);
        }
    }
}

int main() {

    fscanf(fin, "%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        fscanf(fin, "%d %d", &a[i].x, &a[i].y);
    }
    for (int i = 0; i < M; i++) {
        fscanf(fin, "%d %d", &q[i].x, &q[i].y);
    }
    solve();
    
    fclose(fin);
    fclose(fout);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1166 Geometrie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1166 Geometrie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1166 Geometrie