N本の棒（線分）が与えられます。これらの棒は順に入力され、各棒の両端の座標で定義されます。後の棒が前の棒と交差する場合、後の棒は前の棒を「遮る」と見なされます。この問題では、最終的にどの棒にも遮られずに残る棒の数を求めます。

制約として、Nは最大10^5ですが、最終的な解答（遮られない棒の数）は1000を超えないことが保証されています。

幾何アルゴリズムによる解決策

解答が1000を超えないという重要な制約は、一見すると計算量O(N^2)に見える総当たり的なアプローチでも、実際にパフォーマンスの問題を引き起こさないことを示唆しています。各棒について、それより後に入力された全ての棒との交差をチェックし、一つでも交差が見つかればその棒は遮られたと判断できます。

外積の利用

線分の交差判定には、外積（クロス積）が基本的なツールとして用いられます。

1. 定義と幾何学的意味: ベクトル$\vec{a} = (x_1, y_1)$と$\vec{b} = (x_2, y_2)$の外積は、$x_1y_2 - y_1x_2$として計算されます。 これは、2つのベクトルが張る平行四辺形の「符号付き面積」に相当します。$\vec{b}$が$\vec{a}$に対して反時計回りの方向にある場合、外積は正となり、時計回りの場合は負となります。3点が同一直線上にある場合は0になります。
2. 点と直線の位置関係判定: 点$C$が直線$AB$に対してどちら側にあるかを判定するために外積が使えます。 ベクトル$\vec{AB} = B - A$と$\vec{AC} = C - A$の外積$(B-A) \times (C-A)$を計算します。
   • $ > 0 \Rightarrow C$は直線$AB$の左側
   • $ < 0 \Rightarrow C$は直線$AB$の右側
   • $ = 0 \Rightarrow A, B, C$は同一直線上にある

以下に、点の構造体と外積計算のヘルパー関数を示します。

struct Point2D {
    double x_coord, y_coord;
};

// ベクトル減算
Point2D operator-(const Point2D& p1, const Point2D& p2) {
    return {p1.x_coord - p2.x_coord, p1.y_coord - p2.y_coord};
}

// 2つのベクトルの外積を計算
double calc_cross_product(const Point2D& vec_a, const Point2D& vec_b) {
    return vec_a.x_coord * vec_b.y_coord - vec_a.y_coord * vec_b.x_coord;
}

// 点p_cが直線p_a-p_bに対してどちら側にあるかを判定（符号付き面積）
double get_orientation(const Point2D& p_a, const Point2D& p_b, const Point2D& p_c) {
    return calc_cross_product(p_b - p_a, p_c - p_a);
}

線分の交差判定

2つの線分$S_1 = (P_1, P_2)$と$S_2 = (P_3, P_4)$が交差するかどうかは、上記のget_orientation関数を用いて以下のように判定できます。

線分$P_1P_2$と線分$P_3P_4$が交差するためには、以下の2つの条件が両方とも満たされる必要があります。

1. 点$P_3$と$P_4$が線分$P_1P_2$によって異なる側に位置するか、少なくとも一方が線分$P_1P_2$上にある。
2. 点$P_1$と$P_2$が線分$P_3P_4$によって異なる側に位置するか、少なくとも一方が線分$P_3P_4$上にある。

これを外積を使って表現すると、以下のようになります。

• $get\_orientation(P_1, P_2, P_3) \times get\_orientation(P_1, P_2, P_4) \le 0$
• $get\_orientation(P_3, P_4, P_1) \times get\_orientation(P_3, P_4, P_2) \le 0$

両方の条件が同時に真である場合、2つの線分は交差します。これには、端点で接する場合や、同一直線上に重なる場合も含まれます。問題の要件「相交」を満たします。

このロジックを実装した関数は以下のようになります。

// 2つの線分が交差するかどうかを判定
bool do_segments_intersect(const Point2D& s1_a, const Point2D& s1_b,
                           const Point2D& s2_a, const Point2D& s2_b) {
    // 各線分の両端点がもう一方の線分に対してどのように配置されているかを確認
    double o_s1_s2a = get_orientation(s1_a, s1_b, s2_a);
    double o_s1_s2b = get_orientation(s1_a, s1_b, s2_b);
    double o_s2_s1a = get_orientation(s2_a, s2_b, s1_a);
    double o_s2_s1b = get_orientation(s2_a, s2_b, s1_b);

    // 一般的な交差条件: 各線分の両端点がもう一方の線分の異なる側に位置するか、同一直線上にある
    if (o_s1_s2a * o_s1_s2b <= 0 && o_s2_s1a * o_s2_s1b <= 0) {
        // 特別なケースとして、同一直線上にあり、かつ線分が重なっているかを別途考慮することもあるが、
        // この問題では上記の条件で十分とされている (<= 0 がそれをカバーするため)
        return true;
    }
    return false;
}

全体アルゴリズム

全体の処理は以下のようになります。

1. N本の棒の座標を読み込みます。各棒は開始点と終了点（例: stick_start[i], stick_end[i]）で表されます。
2. 結果を格納するためのリスト（例: uncovered_sticks）を用意します。
3. i = 1からNまでの各棒についてループします。
   • 現在の棒iが遮られているかどうかを示すフラグ（例: is_covered）をfalseに初期化します。
   • j = i + 1からNまでの各棒jについてループします。
     • もしstick_iとstick_jが交差する場合（do_segments_intersect(stick_start[i], stick_end[i], stick_start[j], stick_end[j])がtrueを返す場合）、is_coveredをtrueに設定し、内側のループを抜けます（一度でも遮られれば十分です）。
   • もしis_coveredがfalseのままであれば、棒iは遮られていないので、そのインデックスをuncovered_sticksリストに追加します。
4. uncovered_sticksリストの内容を指定されたフォーマットで出力します。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm> // For std::exit

// Point2D 構造体と演算子の定義
struct Point2D {
    double x_coord, y_coord;
};

Point2D operator-(const Point2D& p1, const Point2D& p2) {
    return {p1.x_coord - p2.x_coord, p1.y_coord - p2.y_coord};
}

double calc_cross_product(const Point2D& vec_a, const Point2D& vec_b) {
    return vec_a.x_coord * vec_b.y_coord - vec_a.y_coord * vec_b.x_coord;
}

double get_orientation(const Point2D& p_a, const Point2D& p_b, const Point2D& p_c) {
    return calc_cross_product(p_b - p_a, p_c - p_a);
}

// 2つの線分が交差するかどうかを判定
bool do_segments_intersect(const Point2D& s1_a, const Point2D& s1_b,
                           const Point2D& s2_a, const Point2D& s2_b) {
    double o_s1_s2a = get_orientation(s1_a, s1_b, s2_a);
    double o_s1_s2b = get_orientation(s1_a, s1_b, s2_b);
    double o_s2_s1a = get_orientation(s2_a, s2_b, s1_a);
    double o_s2_s1b = get_orientation(s2_a, s2_b, s1_b);

    if (o_s1_s2a * o_s1_s2b <= 0 && o_s2_s1a * o_s2_s1b <= 0) {
        return true;
    }
    return false;
}

// 問題のメイン処理
void solve_problem() {
    int stick_count;
    while (std::cin >> stick_count && stick_count != 0) {
        std::vector<Point2D> stick_starts(stick_count);
        std::vector<Point2D> stick_ends(stick_count);
        
        for (int i = 0; i < stick_count; ++i) {
            std::cin >> stick_starts[i].x_coord >> stick_starts[i].y_coord
                     >> stick_ends[i].x_coord >> stick_ends[i].y_coord;
        }

        std::vector<int> top_sticks;
        for (int i = 0; i < stick_count; ++i) {
            bool current_stick_is_covered = false;
            // 現在の棒(i)が、それより後に出現する棒(j)によって遮られるかチェック
            for (int j = i + 1; j < stick_count; ++j) {
                if (do_segments_intersect(stick_starts[i], stick_ends[i],
                                          stick_starts[j], stick_ends[j])) {
                    current_stick_is_covered = true;
                    break; // 一度でも交差すれば遮られるため、それ以上チェックする必要はない
                }
            }
            if (!current_stick_is_covered) {
                top_sticks.push_back(i + 1); // 問題の出力は1-indexed
            }
        }

        std::cout << "Top sticks:";
        for (size_t i = 0; i < top_sticks.size(); ++i) {
            std::cout << " " << top_sticks[i];
            if (i < top_sticks.size() - 1) {
                std::cout << ",";
            }
        }
        std::cout << "." << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve_problem();
    return 0;
}