11665 - Chinese Ink

[SRX]

I have considered that one polygon is in the another ... ,
But I am keeping WA , could someone give me some test cases , thanks!

[Chimed]

Could you make a test case then I will give you the correct answer.
By the way polygon intersects when
"Edges of polygons intersect" or "vertexes of a polygon are in an other polygon (fully covered) "

[raincole]

I have considered "Edges of polygons intersect" and "vertexes of a polygon are in an other polygon", but still I got WA...
Could you give me some hint?

Code: Select all

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

#define INF 20000

struct Point {
    int x,y;
   
    Point(int x, int y) : x(x), y(y) {}
    Point(){}
    Point operator - (const Point &a) {
        return Point(x-a.x, y-a.y);
    }
};

struct Polygon {
    int t;
    Point v[10];
};

int N,set[40];
Polygon poly[40];

long long Cross(Point o, Point f, Point s) {
    f = f - o;
    s = s - o;
    return (long long)f.x*s.y - f.y*s.x;
}

bool InSegment(Point a, Point b, Point c) {
    if((long long)(c.x-a.x) * (c.x-b.x) <= 0)
        if(Cross(c, a, b) == 0)
            return 1;
    return 0;
}   

int Intersection(Point a1, Point a2, Point b1, Point b2) {
    long long cross1,cross2,cross3,cross4;
   
    cross1 = Cross(a1, a2, b1);
    cross2 = Cross(a1, a2, b2);
    cross3 = Cross(b1, b2, a1);
    cross4 = Cross(b1, b2, a2);
   
    if(cross1*cross2 < 0 && cross3*cross4 < 0)
        return 1;
    return 0;
}        

bool InPolygon(Polygon p, Point a) {
    int i,j,count,tx,ty;
   
   
    for(i=0; i<p.t; i++)
        if(InSegment(p.v[i], p.v[(i+1)%p.t], a)) {
            return 1;
        }
    tx = INF;
    ty = a.y;
    count = 0;
    for(i=0; i<p.t; i++) {
        count += Intersection(p.v[i], p.v[(i+1)%p.t], a, Point(INF, INF));
    }
    if(count > 0 && count % 2 == 1)    {
        return 1;
    }
    ty += 100;
    count = 0;
    for(i=0; i<p.t; i++) {       
        count += Intersection(p.v[i], p.v[(i+1)%p.t], a, Point(tx, ty));
    }
    if(count > 0 && count % 2 == 1) {
        return 1;
    }
    return 0;
}

int Father(int x) {
    if(set[x] == x)
        return x;
    set[x] = Father(set[x]);
    return set[x];
}

void Union(int x, int y) {
    int fx=Father(x),fy=Father(y);
   
    if(fx != fy)
        set[fx] = fy;
}


int main() {
    int i,j,k,l,ans,count[40];
   
    srand(333667);
    while(scanf("%d", &N) != EOF) {
        if(N == 0)
            break;
        for(i=0; i<N; i++) {
            for(j=0; ; j++) {
                scanf("%d%d", &poly[i].v[j].x, &poly[i].v[j].y);
                if(getchar() == '\n') {
                    poly[i].t = j+1;
                    break;
                }
            }                   
        }
        for(i=0; i<N; i++)
            set[i] = i;
        for(i=0; i<N; i++) {
            for(j=0; j<N; j++) {
                if(i == j)
                    continue;
                for(k=0; k<poly[i].t; k++)
                    if(InPolygon(poly[j], poly[i].v[k])) {
                        Union(i, j);
                    }
                for(k=0; k<poly[i].t; k++)
                    for(l=0; l<poly[j].t; l++)
                        if(Intersection(poly[i].v[k], poly[i].v[(k+1)%poly[i].t],
                                        poly[j].v[l], poly[j].v[(l+1)%poly[j].t]) == 1)
                            Union(i, j);
            }
        }
        ans = 0;
        memset(count, 0, sizeof(count));
        for(i=0; i<N; i++)
            if(count[Father(i)] == 0) {
                count[set[i]] = 1;
                ans++;
            }
        printf("%d\n", ans);
    }
    return 0;
}