直接按照題目意思模擬即可。關鍵是需要實現有理數運算。我的方法是重載運算符。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-10-21 12:25:06
File Name: g.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n)
{for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
struct real
{
int64 a, b;
};
struct point
{
real x, y;
};
int64 gcd(int64 a, int64 b)
{
return b == 0 ? a : gcd(b, a % b);
}
int64 lcm(int64 a, int64 b)
{
return a / gcd(a, b) * b;
}
real operator +(real a, real b)
{
int64 l = lcm(a.b, b.b);
real ret;
ret.a = a.a * l / a.b + b.a * l / b.b;
ret.b = l;
return ret;
}
real operator -(real a, real b)
{
int64 l = lcm(a.b, b.b);
real ret;
ret.a = a.a * l / a.b - b.a * l / b.b;
ret.b = l;
return ret;
}
real operator *(real a, real b)
{
int64 g1 = gcd(a.b, b.a), g2 = gcd(a.a, b.b);
real ret;
ret.a = a.a / g2 * (b.a / g1);
ret.b = a.b / g1 * (b.b / g2);
return ret;
}
real operator /(real a, real b)
{
swap(b.a, b.b);
return a * b;
}
real cross(real a, real b, real c, real d)
{
return a * d - b * c;
}
bool operator ==(real a, real b)
{
return a.a == b.a && a.b == b.b;
}
bool operator ==(point a, point b)
{
return a.x == b.x && a.y == b.y;
}
point inter(point p1, point p2, point p3, point p4)
{
real a11 = p2.y - p1.y;
real a12 = p1.x - p2.x;
real a21 = p4.y - p3.y;
real a22 = p3.x - p4.x;
real b1 = p1.x * p2.y - p2.x * p1.y;
real b2 = p3.x * p4.y - p4.x * p3.y;
point ret;
ret.x = cross(b1, a12, b2, a22) / cross(a11, a12, a21, a22);
ret.y = cross(a11, b1, a12, b2) / cross(a11, a12, a21, a22);
return ret;
}
point p[1000];
int main()
{
int n, m;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int t1, t2;
scanf("%d%d", &t1, &t2);
p[i].x.a = t1;
p[i].x.b = 1;
p[i].y.a = t2;
p[i].y.b = 1;
}
scanf("%d", &m);
int ans = 0;
for (int i = 0; i < m; i++)
{
int t1, t2, t3, t4;
scanf("%d%d%d%d", &t1, &t2, &t3, &t4);
t1--;
t2--;
t3--;
t4--;
point t = inter(p[t1], p[t2], p[t3], p[t4]);
int flag = 1;
for (int j = 0; j < n; j++)
if (t == p[j])
{
flag = 0;
break;
}
if (flag)
p[n++] = t;
if (ans == 0 && t.x.a == 0 && t.y.a == 0)
ans = i + 1;
}
printf("%d\n", ans);
return 0;
}