結果

問題 No.743 Segments on a Polygon
コンテスト
ユーザー vjudge1
提出日時 2025-12-21 16:04:25
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,489 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 616 ms
コンパイル使用メモリ 72,328 KB
実行使用メモリ 20,048 KB
最終ジャッジ日時 2025-12-21 16:04:33
合計ジャッジ時間 8,097 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
// ????????????????????????
bool chordsIntersect(int n, int a, int b, int c, int d) {
    // ??a < b?c < d????????
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
     
    // ??1????????
    if (a == c && b == d) return true;
     
    // ??2??????
    if (a == c || a == d || b == c || b == d) return true;
     
    // ??3?????????
    // ????????(a, b, c, d)????????
    // ??????(c?d?????a-b??????b-a??)
     
    // ????????a???0
    int b1 = (b - a + n) % n;
    int c1 = (c - a + n) % n;
    int d1 = (d - a + n) % n;
     
    // ??a=0?b=b1??0 < b1 < n
    // ??c1?d1?????(0, b1)??????(b1, n)??
    bool c_in_range = (0 < c1 && c1 < b1);
    bool d_in_range = (0 < d1 && d1 < b1);
     
    return (c_in_range != d_in_range);
}
 
// ???????????????
bool chordsIntersect2(int n, int a, int b, int c, int d) {
    // ?????????????????
    vector<int> indices = {a, b, c, d};
     
    // ?????????????????????
    // ???????????????????????????????
     
    // ????????x????(from, to)????????????
    auto isOnArc = [n](int from, int to, int x) -> bool {
        if (from == to) return false;
        if (from < to) {
            return from < x && x < to;
        } else {
            // ???????
            return (from < x && x < n) || (0 <= x && x < to);
        }
    };
     
    // ??c?d??????(a, b)??????(b, a)?
    bool c_in_ab = isOnArc(a, b, c);
    bool d_in_ab = isOnArc(a, b, d);
     
    if (c_in_ab != d_in_ab) {
        return true;  // ????
    }
     
    // ??a?b??????(c, d)??????(d, c)?
    bool a_in_cd = isOnArc(c, d, a);
    bool b_in_cd = isOnArc(c, d, b);
     
    if (a_in_cd != b_in_cd) {
        return true;  // ????
    }
     
    // ?????????
    if (a == c || a == d || b == c || b == d) {
        return true;  // ????
    }
     
    return false;
}
 
// ????
int main() {
    //chordsIntersect(8, 0, 4, 1, 5) ;
    int n,m;
    cin>>n>>m;
    int cnt=0;
    int k[100010][2];
    for(int i=0;i<n;i++){
        cin>>k[i][0]>>k[i][1];
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(chordsIntersect(m,k[i][0],k[i][1],k[j][0],k[j][1])){
                cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}
/**************************************************************
    Problem: 10966
    User: liuqiyuan2
    Language: C++
    Result: ??
****************************************************************/
0