Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement