結果

問題 No.245 貫け！
コンテスト
ユーザー mamekin
提出日時 2016-01-30 14:44:12
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,606 bytes
コンパイル時間 1,429 ms
コンパイル使用メモリ 96,124 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-21 19:11:23
合計ジャッジ時間 1,994 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class Point
{
public:
    int y, x;
    Point(){
        y = x = 0;
    }
    Point(int y0, int x0){
        y = y0;
        x = x0;
    }
    Point operator+(const Point& p) const{
        return Point(y + p.y, x + p.x);
    }
    Point operator-(const Point& p) const{
        return Point(y - p.y, x - p.x);
    }
    Point operator*(int a) const{
        return Point(y * a, x * a);
    }
    long long length2() const{
        return y * (long long)y + x * (long long)x;
    }
    long long dist2(const Point& p) const{
        return (y - p.y) * (long long)(y - p.y) + (x - p.x) * (long long)(x - p.x);
    }
    long long dot(const Point& p) const{
        return y * (long long)p.y + x * (long long)p.x; // |a|*|b|*cosθ
    }
    long long cross(const Point& p) const{
        return x * (long long)p.y - y * (long long)p.x; // |a|*|b|*sinθ
    }
    bool operator==(const Point& p) const{
        return x == p.x && y == p.y;
    }
};

bool segmentsCollide(const Point& a1, const Point& a2, const Point& b1, const Point& b2)
{
    if(min(a1.x, a2.x) > max(b1.x, b2.x) || min(b1.x, b2.x) > max(a1.x, a2.x) || min(a1.y, a2.y) > max(b1.y, b2.y) || min(b1.y, b2.y) > max(a1.y, a2.y))
        return false;

    long long c = (a2-a1).cross(b1-a1);
    long long d = (a2-a1).cross(b2-a1);
    long long e = (b2-b1).cross(a1-b1);
    long long f = (b2-b1).cross(a2-b1);
    return (c == 0 || d == 0 || ((c < 0) ^ (d < 0))) && (e == 0 || f == 0 || ((e < 0) ^ (f < 0)));
}

int main()
{
    int n;
    cin >> n;
    vector<vector<Point> > p(n, vector<Point>(2));
    for(int i=0; i<n; ++i){
        for(int j=0; j<2; ++j){
            cin >> p[i][j].y >> p[i][j].x;
        }
    }

    int ans = 0;
    for(int i=0; i<n; ++i){
        for(int j=i; j<n; ++j){
            for(int k=0; k<4; ++k){
                Point a = p[i][k/2];
                Point b = p[j][k%2];
                if(a == b)
                    continue;

                int cnt = 0;
                for(int l=0; l<n; ++l){
                    if(segmentsCollide(a, b, p[l][0], p[l][1]))
                        ++ cnt;
                }
                ans = max(ans, cnt);
            }
        }
    }
    cout << ans << endl;

    return 0;
}
0