Pagini recente » Concursuri Virtuale | Cod sursa (job #303626)
Cod sursa(job #303626)
#include <cstdio>
#define MAX_N 1005
#define INF 1000000.0
struct point
{
double x, y;
};
struct line
{
int a, b, c;
} A[MAX_N];
typedef struct nod
{
int x, y;
nod *next;
} *list;
list H[MAX_N];
int N, M, K = 1;
void add(list &L, int x, int y)
{
list t = new nod;
t -> x = x;
t -> y = y;
t -> next = L;
L = t;
}
void citire()
{
scanf("%d %d",&N, &M);
for(int i = 1; i <= N; ++i)
scanf("%d %d %d", &A[i].a, &A[i].b, &A[i].c);
for(int i = 1; i <= M; ++i)
{
int x, y;
scanf("%d %d",&x, &y);
add(H[1], x, y);
}
}
int sign(point p0, point p1, point p2)
{
double t = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
if(t >= 0) return 1;
return -1;
}
int a, b, c;
void solve()
{
for(int i = 1; i <= N; ++i)
{
a = A[i].a;
b = A[i].b;
c = A[i].c;
point p0, p1, p2;
if(b == 0)
p1.x = -(double)c / a,
p1.y = 0.0;
else
p1.x = 0.0,
p1.y = -(double)c / b;
if(b == 0)
p2.x = -(double)c / a,
p2.y = 1.0;
else
p2.x = 1.0,
p2.y = -(double)(c + a) / b;
int k = K;
for(int j = 1; j <= k; ++j)
{
if(H[j] == NULL) continue;
p0.x = H[j] -> x;
p0.y = H[j] -> y;
bool ok = 0;
int s = sign(p0, p1, p2);
for(list p = H[j]; p -> next;)
{
p0.x = p -> next -> x;
p0.y = p -> next -> y;
if(sign(p0, p1, p2) != s)
{
list aux = p -> next;
p -> next = aux -> next;
if(!ok) ++K, ok = 1;
add(H[K], aux -> x, aux -> y);
delete aux;
}
else
p = p -> next;
}
}
#ifdef _HOME_
for(int i = 1; i <= 3; ++i)
{
for(list p = H[i]; p; p = p -> next)
fprintf(stderr, "%d %d ", p -> x, p -> y);
fprintf(stderr, "\n");
}
#endif
}
int Sol = 0;
for(int i = 1; i <= M; ++i)
if(H[i]) ++Sol;
printf("%d\n",Sol);
}
int main()
{
freopen("regiuni.in","rt",stdin);
freopen("regiuni.out","wt",stdout);
citire();
solve();
}