#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct P { typedef int T; typedef ll T2; //T2は{a*b | a:T, b:T}を含むタイプ T x, y; P(T x_, T y_): x(x_), y(y_) {} P(): x(0), y(0) {} }; inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; } inline bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); } inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); } inline P operator-=(P& a, const P& b) { a.x -= b.x, a.y -= b.y ; return a; } inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; } inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; } inline P::T2 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; } ostream& operator<<(ostream& out, const P& x) { out << "(" << x.x << ", " << x.y << ")"; return out; } int compareAngle(const P &a, const P &b) { int za = a.y > 0 || (a.y == 0 && a.x > 0) ? 0 : 1; int zb = b.y > 0 || (b.y == 0 && b.x > 0) ? 0 : 1; if(za != zb) return za - zb; P::T2 t1 = (P::T2)a.x * b.y; P::T2 t2 = (P::T2)a.y * b.x; return t1 > t2 ? 1 : t1 < t2 ? -1 : 0; } struct Angle { P point; int infty; int eps; Angle(): point(), infty(0), eps(0) { } Angle(P::T x, P::T y, int eps_ = 0): point(P(x, y)), infty(0), eps(eps_) { } Angle(P point_, int eps_ = 0): point(point_), infty(0), eps(eps_) { } Angle(P origin, P target, int eps_ = 0): point(target.x - origin.x, target.y - origin.y), infty(0), eps(eps_) { } explicit Angle(int infty_): point(), infty(infty_), eps(0) { } bool zero() const { return point.x == 0 && point.y == 0; } int compare_to(const Angle &that) const { if(infty != 0) return that.infty == 0 ? infty : (infty > 0) - (that.infty > 0); else if(that.infty != 0) return -that.infty; assert(!zero() && !that.zero()); int t = compareAngle(point, that.point); if(t != 0) return t; return eps == that.eps ? 0 : eps > that.eps ? 1 : -1; } bool operator==(const Angle &that) const { return compare_to(that) == 0; } bool operator!=(const Angle &that) const { return compare_to(that) != 0; } bool operator< (const Angle &that) const { return compare_to(that) < 0; } bool operator<=(const Angle &that) const { return compare_to(that) <= 0; } bool operator> (const Angle &that) const { return compare_to(that) > 0; } bool operator>=(const Angle &that) const { return compare_to(that) >= 0; } friend ostream &operator<<(ostream &o, const Angle &a) { if(a.infty != 0) return o << (a.infty > 0 ? "+" : "-") << "oo"; o << "(" << a.point.x << ", " << a.point.y << ")"; if(a.eps != 0) o << a.eps; return o; } Angle operator-() const { if(infty != 0) return Angle(-infty); return Angle(-point.x, -point.y, -eps); } bool unordered_sandwich(Angle a, Angle b) const { if(a.zero() || b.zero() || a == -b) return true; if(a < -a) { if(-a < b || b < a) swap(a, b); }else { if(-a < b && b < a) swap(a, b); } return ordered_sandwich(a, b); } bool ordered_sandwich(Angle a, Angle b) const { if(a <= b) return a <= *this && *this <= b; else return a <= *this || *this <= b; } }; int main() { int N; while(~scanf("%d", &N)) { vector

ps; vector > segs(N); rep(i, N) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); segs[i] = mp(P(a, b), P(c, d)); ps.push_back(P(a, b)); ps.push_back(P(c, d)); } int ans = 0; rep(i, ps.size()) { P org = ps[i]; int cnt = 0; vector > angles; Angle inita(P(1, 0), -1); rep(j, N) { Angle a(org, segs[j].first), b(org, segs[j].second); if(a.zero() || b.zero() || a == -b) { ++ cnt; }else { angles.push_back(mp(a, j)); angles.push_back(mp(b, N + j)); if(inita.unordered_sandwich(a, b)) ++ cnt; } } sort(all(angles)); amax(ans, cnt); for(int j = 0; j < (int)angles.size(); ++ j) { if(angles[j].second / N == 0) ++ cnt; else -- cnt; // cerr << i << ", " << j << ": " << cnt << endl; amax(ans, cnt); } } printf("%d\n", ans); } return 0; }