## 11665 - Chinese Ink

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### 11665 - Chinese Ink

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

Chimed
New poster
Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

### Re: 11665 Chinese Ink

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
New poster
Posts: 6
Joined: Wed Sep 23, 2009 4:42 pm

### Re: 11665 Chinese Ink

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;
}