結果

問題 No.245 貫け！
ユーザー Mao-beta
提出日時 2025-02-13 01:41:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,118 ms / 5,000 ms
コード長 2,504 bytes
コンパイル時間 1,169 ms
コンパイル使用メモリ 99,260 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-13 01:41:33
合計ジャッジ時間 20,602 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct Segment {
    int a, b, c, d;
};

struct Point {
    int x, y;
};

// 2次元ベクトルの外積を計算
inline ll cross(ll ax, ll ay, ll bx, ll by) {
    return ax * by - ay * bx;
}

// check 関数：直線 PQ が、点 R と S の間を通るか？
int check(const Point &P, const Point &Q, const Point &R, const Point &S) {
    // PとQが同一なら何も意味がないので 0 を返す
    if(P.x == Q.x && P.y == Q.y) return 0;
    // ベクトル PQ, PR, PS を計算
    ll pqx = Q.x - P.x, pqy = Q.y - P.y;
    ll prx = R.x - P.x, pry = R.y - P.y;
    ll psx = S.x - P.x, psy = S.y - P.y;
    // cross(PQ, PR) と cross(PQ, PS) の積が 0 以下なら、R と S は直線 PQ の両側（または PQ 上）にある
    ll cross1 = cross(pqx, pqy, prx, pry);
    ll cross2 = cross(pqx, pqy, psx, psy);
    return (cross1 * cross2 <= 0) ? 1 : 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<Segment> segs(N);
    for (int i = 0; i < N; i++) {
        cin >> segs[i].a >> segs[i].b >> segs[i].c >> segs[i].d;
    }
    
    int ans = 0;
    // 候補となる点 (px, py) を全探索 (-101 <= px,py <= 101)
    for (int px = -101; px <= 101; px++){
        for (int py = -101; py <= 101; py++){
            Point P {px, py};
            // 各線分について、両端点それぞれを Q としてチェック
            for (int i = 0; i < N; i++){
                int tmp = 0;
                // まずは線分 i の左側の端点を Q とする
                Point Q {segs[i].a, segs[i].b};
                // 全ての線分について、直線 PQ が分断しているかを調べる
                for (int j = 0; j < N; j++){
                    Point R {segs[j].a, segs[j].b};
                    Point S {segs[j].c, segs[j].d};
                    tmp += check(P, Q, R, S);
                }
                ans = max(ans, tmp);

                // 次は線分 i の右側の端点を Q とする
                tmp = 0;
                Q = {segs[i].c, segs[i].d};
                for (int j = 0; j < N; j++){
                    Point R {segs[j].a, segs[j].b};
                    Point S {segs[j].c, segs[j].d};
                    tmp += check(P, Q, R, S);
                }
                ans = max(ans, tmp);
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}
0