#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; } struct L { P a, b; L() { } L(const P &a_, const P &b_): a(a_), b(b_) {} const P& operator[](size_t i) const { return i ? b : a; } }; inline int ccw(const P& a, const P& b, const P& c) { int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y; P::T2 t = (P::T2)ax*by - (P::T2)ay*bx; if (t > 0) return 1; if (t < 0) return -1; if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2; if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2; return 0; } //問題ごとに線分のオーバーラップなどを考えて書き換えること //!同じ"点を共有している"であっても3ならOKで2は駄目であることも多いので注意! //線分が点になっているケースではcontainsSPで別個にやらないとだめ!!!!!!!!!!! //完全に交差している : 0 //点を共有している : 2, 3 //線分を共有している : 0 //共有点は無い : 1 int intersectSS(const L &s, const L &t) { assert(!(s.a == s.b || t.a == t.b)); int a = ccw(s.a,s.b,t.a), b = ccw(s.a,s.b,t.b), c = ccw(t.a,t.b,s.a), d = ccw(t.a,t.b,s.b); int x = a * b, y = c * d; if(x == -1 && y == -1) return 0; //cross else if( ((abs(b) == 1 || b == -2) && s.b == t.a) || ((abs(b) == 1 || b == 2) && s.a == t.a) || ((abs(a) == 1 || a == -2) && s.b == t.b) || ((abs(a) == 1 || a == 2) && s.a == t.b) ) return 2; // point overlap (真ん中と端を共有する) else if( (x == 0 && (abs(a) + abs(b) == 1)) || (y == 0 && (abs(c) + abs(d) == 1)) ) return 3; // point overlap (端点のみを共有する) else if(x <= 0 && y <= 0) return 0; //segment overlap else return 1; } int main() { int N; while(cin >> N) { vector segs(N); vector

ps; rep(i, N) { int a, b, c, d; cin >> a >> b >> c >> d; segs[i] = L(P(a, b), P(c, d)); ps.push_back(P(a, b)); ps.push_back(P(c, d)); } sort(all(ps)); ps.erase(unique(all(ps)), ps.end()); int ans = 0; rep(i, ps.size()) rep(j, ps.size()) if(i != j) { P d = ps[j] - ps[i]; P dd(d.x * 10000, d.y * 10000); L seg(ps[i] - dd, ps[j] + dd); int cnt = 0; rep(k, N) cnt += intersectSS(seg, segs[k]) != 1; amax(ans, cnt); } cout << ans << endl; } return 0; }