結果

問題 No.245 貫け！
ユーザー not_522
提出日時 2015-08-17 15:04:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 8,595 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 167,340 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-18 10:00:55
合計ジャッジ時間 2,417 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
namespace arithmetic {
  template<typename T> class Addition {
  public:
    template<typename V> T operator+(const V& v) const {
      return T(static_cast<const T&>(*this)) += v;
    }
  };
  template<typename T> class Subtraction {
  public:
    template<typename V> T operator-(const V& v) const {
      return T(static_cast<const T&>(*this)) -= v;
    }
  };
  template<typename T> class Multiplication {
  public:
    template<typename V> T operator*(const V& v) const {
      return T(static_cast<const T&>(*this)) *= v;
    }
  };
  template<typename T> class Division {
  public:
    template<typename V> T operator/(const V& v) const {
      return T(static_cast<const T&>(*this)) /= v;
    }
  };
  template<typename T> class Modulus {
  public:
    template<typename V> T operator%(const V& v) const {
      return T(static_cast<const T&>(*this)) %= v;
    }
  };
}
template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic
    ::Multiplication<T> {};
template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};
template<typename T> class Ordered {
public:
  template<typename V> bool operator==(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
  }
  
  template<typename V> bool operator!=(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
  }
  template<typename V> bool operator>(const V& v) const {
    return static_cast<T>(v) < static_cast<const T&>(*this);
  }
  template<typename V> bool operator<=(const V& v) const {
    return !(static_cast<T>(v) < static_cast<const T&>(*this));
  }
  template<typename V> bool operator>=(const V& v) const {
    return !(static_cast<const T&>(*this) < static_cast<T>(v));
  }
};
template<typename T> inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template<typename T> inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template<typename T> inline T floor(T a, T b) {
  return floor(a / b) * b <= a ? floor(a / b) : floor(a / b) - 1;
}
template<typename T> inline T ceil(T a, T b) {
  return floor(a + b - 1, b);
}
template<typename T> inline T round(T a, T b) {
  return floor(a + b / 2);
}
template<typename T> inline T mod(T a, T b) {
  return a - floor(a, b) * b;
}
template<typename T> inline T factorial(T n) {
  return n <= 1 ? 1 : factorial(n - 1) * n;
}
class Real : public Arithmetic<Real>, public arithmetic::Modulus<Real>, public Ordered<Real> {
private:
  static long double EPS;
  long double val;
  operator long double() const {
    return val;
  }
public:
  Real() {}
  Real(long double val) : val(val) {}
  Real operator-() const {
    return -val;
  }
  template<typename T> Real operator+=(const T& r) {
    val += static_cast<long double>(r);
    return *this;
  }
  template<typename T> Real operator-=(const T& r) {
    val -= static_cast<long double>(r);
    return *this;
  }
  template<typename T> Real operator*=(const T& r) {
    val *= static_cast<long double>(r);
    return *this;
  }
  template<typename T> Real operator/=(const T& r) {
    val /= static_cast<long double>(r);
    return *this;
  }
  template<typename T> Real operator%=(const T& r) {
    return *this = mod(*this, static_cast<Real>(r));
  }
  template<typename T> Real operator-(const T& v) const {
    return Real(*this) -= v;
  }
  template<typename T> Real operator*(const T& v) const {
    return Real(*this) *= v;
  }
  template<typename T> Real operator/(const T& v) const {
    return Real(*this) /= v;
  }
  template<typename T> bool operator<(const T r) const {
    return val < static_cast<long double>(r) - EPS;
  }
  Real abs() const {
    return std::abs(val);
  }
  Real sqrt() const {
    return std::sqrt(val);
  }
  long double toLongDouble() const {
    return val;
  }
};
long double Real::EPS = 1e-10;
inline ostream& operator<<(ostream& os, const Real& a) {
  os << fixed << setprecision(15) << a.toLongDouble();
  return os;
}
inline istream& operator>>(istream& is, Real& a) {
    long double n;
    is >> n;
    a = n;
    return is;
}
Real floor(const Real& r) {
  return floor(r.toLongDouble());
}
class Point : public Arithmetic<Point>, public Ordered<Point> {
public:
  Real x, y;
  Point() {}
  Point(const Real& x) : x(x), y(0) {}
  Point(const Real& x, const Real& y) : x(x), y(y) {}
  Point operator+=(const Point& p) {
    x += p.x;
    y += p.y;
    return *this;
  }
  Point operator-=(const Point& p) {
    x -= p.x;
    y -= p.y;
    return *this;
  }
  Point operator*=(const Point& p) {
    Real xx = x * p.x - y * p.y;
    y = x * p.y + y * p.x;
    x = xx;
    return *this;
  }
  Point operator*=(const Real& r) {
    x *= r;
    y *= r;
    return *this;
  }
  Point operator/=(const Point& p) {
    Real nrm = p.norm();
    Real xx = (x * p.x + y * p.y) / nrm;
    y = (y * p.x - x * p.y) / nrm;
    x = xx;
    return *this;
  }
  Point operator/=(const Real& r) {
    x /= r;
    y /= r;
    return *this;
  }
  bool operator<(const Point& p) const {
    return (x == p.x) ? y < p.y : x < p.x;
  }
  Real norm() const {
    return x * x + y * y;
  }
  Real abs() const {
    return norm().sqrt();
  }
  Point conj() const {
    return Point(x, -y);
  }
};
inline Point operator*(const Real& real, const Point& point) {
  return point * real;
}
inline Point operator/(const Real& real, const Point& point) {
  return point / real;
}
inline ostream& operator<<(ostream& os, const Point& point) {
    os << point.x << " " << point.y;
    return os;
}
inline istream& operator>>(istream& is, Point& point) {
  Real x, y;
    is >> x >> y;
    point = Point(x, y);
    return is;
}
class Line {
public:
  Point a, b;
  Line() {}
  Line (const Point& a, const Point& b) : a(a), b(b) {}
  bool operator==(const Line& line) const {
    return ((line.vec() / vec()).y == 0) && (((line.a - a) / vec()).y == 0);
  }
  Point vec() const {
    return b - a;
  }
};
inline ostream& operator<<(ostream& os, const Line& line) {
    os << line.a << " " << line.b;
    return os;
}
inline istream& operator>>(istream& is, Line& line) {
  Point a, b;
  is >> a >> b;
  line = Line(a, b);
  return is;
}
class Segment : public Line, public Ordered<Segment> {
public:
  Segment() {}
  Segment (const Point& a, const Point& b) : Line(a, b) {}
  bool operator<(const Segment& segment) const {
    return a == segment.a ? b < segment.b : a < segment.a;
  }
};
enum CCW{LEFT = 1, RIGHT = 2, BACK = 4, FRONT = 8, ON = 16};
int ccw(const Point& a, const Point& b, const Point& c) {
  Point p = (c - a) / (b - a);
  if (p.y > 0) return LEFT;
  if (p.y < 0) return RIGHT;
  if (p.x < 0) return BACK;
  if (p.x > 1) return FRONT;
  return ON;
}
int ccw(const Segment& segment, const Point& point) {
  return ccw(segment.a, segment.b, point);
}
int ccw(const Line& line, const Point& point) {
  int res = ccw(line.a, line.b, point);
  if (res == BACK || res == FRONT) res = ON;
  return res;
}
template<bool strict = false> inline bool intersect(const Line& line1, const Line& line2) {
  if (strict) return (line1.vec() / line2.vec()).y != 0;
  return ((line1.vec() / line2.vec()).y != 0) || (line1 == line2);
}
template<bool strict = false> inline bool intersect(const Line& line, const Segment& segment) {
  Point p1 = (segment.a - line.a) / line.vec(), p2 = (segment.b - line.a) / line.vec();
  if (strict) return p1.y * p2.y < 0;
  return p1.y * p2.y <= 0;
}
template<bool strict = false> inline bool intersect(const Segment& segment, const Line& line) {
  return intersect(line, segment);
}
template<bool strict = false> inline bool intersect(const Segment& segment1, const Segment& segment2) {
  int ccw1 = ccw(segment1, segment2.a) | ccw(segment1, segment2.b);
  int ccw2 = ccw(segment2, segment1.a) | ccw(segment2, segment1.b);
  if (strict) return (ccw1 & ccw2) == (LEFT | RIGHT);
  return ((ccw1 & ccw2) == (LEFT | RIGHT)) || ((ccw1 | ccw2) & ON);
}
int main() {
  int n;
  cin >> n;
  vector<Segment> s(n);
  for (auto& i : s) cin >> i;
  vector<Point> p(2 * n);
  for (int i = 0; i < n; ++i) {
    p[i] = s[i].a;
    p[i + n] = s[i].b;
  }
  int res = 0;
  for (const auto& a : p) {
    for (const auto& b : p) {
      if (a == b) continue;
      Line line(a, b);
      int cnt = 0;
      for (const auto& k : s) {
        if (intersect(line, k)) ++cnt;
      }
      res = max(res, cnt);
    }
  }
  cout << res << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0