Ion și Gheorghe au primit moștenire două parcele de pământ de formă poligonală. Într-o zi, Ion l-a văzut pe Gheorghe că a folosit o parte din bucata lui. Certându-se, aceștia au remarcat că acea bucată era parte din moștenirea amândurora. Au hotărât să se ducă la judecată și să se rezolve eroarea care a făcut ca parcelele moștenite să se intersecteze. Dar cum procesul va începe destul de târziu, au hotărât să nu folosească acea bucată comună până nu va fi rezolvată problema.

Cerința

Dându-se coordonatele vârfurilor celor două parcele, care au formă de poligon convex, să se afle coordonatele vârfurilor părții comune.

Date de intrare

Pe prima linie a fișierului de intrare parcele.in se găsește un număr natural N. Pe următoarele N linii se găsesc perechi de numere întregi ce reprezintă coordonatele vârfurilor primului poligon. Pe a N+2-a linie se găsește un număr natural M, reprezentând numărul de vârfuri al celui de-al doilea poligon. Următoarele M linii conțin perechi de numere întregi ce reprezintă coordonatele vârfurilor celui de-al doilea poligon. În fiecare listă de perechi, două perechi consecutive formează o latură a poligonului respectiv. De asemenea, ultima și prima dintre perechile din fiecare listă determină o latură. Vârfurile sunt date în sens trigonometric.

Date de ieșire

Pe prima linie a fișierului de ieșire parcele.out se va găsi un număr natural P, iar pe următoarele P linii perechi de numere reale cu două zecimale exacte ce reprezintă coordonatele părții comune. Două perechi consecutive trebuie să determine o latură a poligonului, dar și ultima pereche cu prima trebuie să determine o latură.

Restricții și precizări

3 ≤ N, M ≤ 1.000
coordonatele au valori între -100.000 și 100.000
cele două poligoane au intersecția de arie pozitivă
niciun poligon nu este inclus în celălalt
se acordă 30% din punctaj pentru aflarea lui P

Exemplu

parcele.in

parcele.out

Explicație

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 parcele:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct { double x, y; } vec_t, *vec;

inline double dot(vec a, vec b)
{
    return a->x * b->x + a->y * b->y;
}

inline double cross(vec a, vec b)
{
    return a->x * b->y - a->y * b->x;
}

inline vec vsub(vec a, vec b, vec res)
{
    res->x = a->x - b->x;
    res->y = a->y - b->y;
    return res;
}

int left_of(vec a, vec b, vec c)
{
    vec_t tmp1, tmp2;
    double x;
    vsub(b, a, &tmp1);
    vsub(c, b, &tmp2);
    x = cross(&tmp1, &tmp2);
    return x < 0 ? -1 : x > 0;
}

int line_sect(vec x0, vec x1, vec y0, vec y1, vec res)
{
    vec_t dx, dy, d;
    vsub(x1, x0, &dx);
    vsub(y1, y0, &dy);
    vsub(x0, y0, &d);
    double dyx = cross(&dy, &dx);
    if (!dyx) return 0;
    dyx = cross(&d, &dx) / dyx;
    if (dyx <= 0 || dyx >= 1) return 0;

    res->x = y0->x + dyx * dy.x;
    res->y = y0->y + dyx * dy.y;
    return 1;
}

typedef struct { int len, alloc; vec v; } poly_t, *poly;

poly poly_new()
{
    return (poly)calloc(1, sizeof(poly_t));
}

void poly_free(poly p)
{
    free(p->v);
    free(p);
}

void poly_append(poly p, vec v)
{
    if (p->len >= p->alloc) {
        p->alloc *= 2;
        if (!p->alloc) p->alloc = 4;
        p->v = (vec)realloc(p->v, sizeof(vec_t) * p->alloc);
    }
    p->v[p->len++] = *v;
}

int poly_winding(poly p)
{
    return left_of(p->v, p->v + 1, p->v + 2);
}

void poly_edge_clip(poly sub, vec x0, vec x1, int left, poly res)
{
    int i, side0, side1;
    vec_t tmp;
    vec v0 = sub->v + sub->len - 1, v1;
    res->len = 0;

    side0 = left_of(x0, x1, v0);
    if (side0 != -left) poly_append(res, v0);

    for (i = 0; i < sub->len; i++) {
        v1 = sub->v + i;
        side1 = left_of(x0, x1, v1);
        if (side0 + side1 == 0 && side0)
            if (line_sect(x0, x1, v0, v1, &tmp))
                poly_append(res, &tmp);
        if (i == sub->len - 1) break;
        if (side1 != -left) poly_append(res, v1);
        v0 = v1;
        side0 = side1;
    }
}

poly poly_clip(poly sub, poly clip)
{
    int i;
    poly p1 = poly_new(), p2 = poly_new(), tmp;

    int dir = poly_winding(clip);
    poly_edge_clip(sub, clip->v + clip->len - 1, clip->v, dir, p2);
    for (i = 0; i < clip->len - 1; i++) {
        tmp = p2; p2 = p1; p1 = tmp;
        if(p1->len == 0) {
            p2->len = 0;
            break;
        }
        poly_edge_clip(p1, clip->v + i, clip->v + i + 1, dir, p2);
    }

    poly_free(p1);
    return p2;
}

vec_t *citire_poligon(int *vlen)
{
    scanf("%d", vlen);
    vec_t *v;
    v = (vec_t *)malloc(*vlen * sizeof(vec_t));
    int i;
    for (i = 0; i < *vlen; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        v[i].x = x;
        v[i].y = y;
    }
    return v;
}

int main()
{
    int i;
    freopen("parcele.in", "r", stdin);
    freopen("parcele.out", "w", stdout);
    vec_t *c, *s;
    int clen, slen;
    c = citire_poligon(&clen);
    s = citire_poligon(&slen);

    poly_t clipper = {clen, 0, c};
    poly_t subject = {slen, 0, s};

    poly res = poly_clip(&subject, &clipper);

    printf("%d\n", res->len);
    for (i = 0; i < res->len; i++)
        printf("%0.2lf %0.2lf\n", res->v[i].x, res->v[i].y);

    free(c);
    free(s);
    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 #1977 parcele

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1977 parcele 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 #1977 parcele