POJ 3429 - Geometry with a ruler

http://poj.org/problem?id=3429

概要

二次元座標上の \(N\) 個の点が与えられる。

この後、「a 番目と b 番目の点を結んだ直線と、c 番目と d 番目の点を結んだ直線の交点を求めよ」という命令が \(M\) 個くる。 \(k\) 番目の命令によってできた交点は \(N+k\) 番目の点と呼び、以降の命令で参照されることがある。

このとき、一番最初に原点と一致する交点は何番目の命令によって得られるかを答える。 ただし、どの命令によっても得られない場合は 0 と答える。

制約

解法

やるだけだが、double でやると精度が足りなくて WA。 long long の有理数でオーバーフローに注意しながら計算して通った。

  1 #include <iostream>
  2 #include <vector>
  3 #include <complex>
  4 using namespace std;
  5 
  6 long long gcd(long long a, long long b)
  7 {
  8   if (a < b) {
  9     swap(a, b);
 10   }
 11   if (b == 0LL) {
 12     return a;
 13   }
 14   long long r;
 15   while ((r = a % b) != 0LL) {
 16     a = b;
 17     b = r;
 18   }
 19   return b;
 20 }
 21 
 22 struct ratio/*{{{*/
 23 {
 24   long long n, d;
 25   ratio() : n(0), d(1) {}
 26   ratio(long long x) : n(x), d(1) {}
 27   ratio(long long a, long long b) : n(a), d(b)
 28   {
 29     const long long g = gcd(a, b);
 30     n /= g;
 31     d /= g;
 32     normalize();
 33   }
 34 
 35   void normalize()
 36   {
 37     if (d < 0) {
 38       n = -n;
 39       d = -d;
 40     }
 41   }
 42 
 43   bool operator==(const ratio& r) const { return n == r.n && d == r.d; }
 44   ratio inverse() const { return ratio(d, n); }
 45 
 46   ratio& operator+=(const ratio& r)
 47   {
 48     const long long g = gcd(d, r.d);
 49     const long long dd = d / g * r.d;
 50     const long long nn = r.d/g*n + d/g*r.n;
 51     d = dd;
 52     n = nn;
 53     normalize();
 54     return *this;
 55   }
 56   ratio& operator-=(const ratio& r) { return *this += ratio(-r.n, r.d); }
 57   ratio& operator*=(const ratio& r)
 58   {
 59     const long long g1 = gcd(n, r.d), g2 = gcd(d, r.n);
 60     n = (n/g1) * (r.n/g2);
 61     d = (d/g2) * (r.d/g1);
 62     normalize();
 63     return *this;
 64   }
 65   ratio& operator/=(const ratio& r) { return *this *= r.inverse(); }
 66   ratio operator+(const ratio& r) const { ratio t(*this); return t += r; }
 67   ratio operator-(const ratio& r) const { ratio t(*this); return t -= r; }
 68   ratio operator*(const ratio& r) const { ratio t(*this); return t *= r; }
 69   ratio operator/(const ratio& r) const { ratio t(*this); return t /= r; }
 70 };
 71 ostream& operator<<(ostream& os, const ratio& r)
 72 {
 73   if (r.d == 1) {
 74     return os << r.n;
 75   } else {
 76     return os << r.n << '/' << r.d;
 77   }
 78 }/*}}}*/
 79 
 80 typedef complex<ratio> P;
 81 
 82 inline ratio cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 83 
 84 struct line/*{{{*/
 85 {
 86   P a, b;
 87   line() {}
 88   line(const P& p, const P& q) : a(p), b(q) {}
 89 
 90   inline P intersection(const line& ln) const
 91   {
 92     // assert(intersects(ln))
 93     const P x = b - a;
 94     const P y = ln.b - ln.a;
 95     return a + cross(y, ln.a - a)/cross(y, x)*x;
 96   }
 97 };/*}}}*/
 98 
 99 struct quad { int a, b, c, d; };
100 
101 int solve(vector<P>& ps, const vector<quad>& qs)
102 {
103   const int M = qs.size();
104   for (int i = 0; i < M; i++) {
105     const P p = line(ps[qs[i].a], ps[qs[i].b]).intersection(line(ps[qs[i].c], ps[qs[i].d]));
106     const ratio r = p.real(), t = p.imag();
107     if (r == ratio(0) && t == ratio(0)) {
108       return i+1;
109     }
110     ps.push_back(p);
111   }
112   return 0;
113 }
114 
115 int main()
116 {
117   int N;
118   cin >> N;
119   vector<P> ps;
120   for (int i = 0; i < N; i++) {
121     long long x, y;
122     cin >> x >> y;
123     ps.push_back(P(x, y));
124   }
125   int M;
126   cin >> M;
127   vector<quad> qs(M);
128   for (int i = 0; i < M; i++) {
129     cin >> qs[i].a >> qs[i].b >> qs[i].c >> qs[i].d;
130     --qs[i].a;  --qs[i].b;  --qs[i].c;  --qs[i].d;
131   }
132   cout << solve(ps, qs) << endl;
133   return 0;
134 }
poj/3429.cc