Submission #1176019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176019		gebyjaff	Dragon 2 (JOI17_dragon2)	C++20	15 / 100	4094 ms	1380 KiB

dragon2

#include <iostream>
#include <vector>
// #include <map> // map is not used in this version

// Define Point structure using long long for coordinates to handle large values
struct Point {
    long long x, y;
};

// Define Dragon structure storing its position and tribe ID
struct Dragon {
    Point p;
    int tribe;
};

// Function to calculate the orientation of three points (P, Q, R)
// It computes the cross product of vectors PQ and PR.
// Returns a positive value if R is to the left of the directed line PQ.
// Returns a negative value if R is to the right of the directed line PQ.
// Returns zero if P, Q, R are collinear.
// Uses long long arithmetic throughout to avoid overflow issues with large coordinates.
long long orient(Point P, Point Q, Point R) {
    // Calculate coordinate differences using long long
    long long Qx_Px = Q.x - P.x;
    long long Ry_Py = R.y - P.y;
    long long Qy_Py = Q.y - P.y;
    long long Rx_Px = R.x - P.x;
    
    // Calculate the cross product (determinant).
    // The coordinates can be up to 10^9, so differences can be up to 2*10^9.
    // The product of two differences can be up to (2*10^9)^2 = 4*10^18.
    // This fits within a 64-bit signed long long which has a maximum value of approx 9*10^18.
    long long val = Qx_Px * Ry_Py - Qy_Py * Rx_Px;
    return val;
}

// Function to check if the ray starting from Ai, passing through Ak, intersects the line segment P1P2.
bool check_intersection(Point Ai, Point Ak, Point P1, Point P2) {
    // Calculate necessary orientations. O_ik_1 checks P1 relative to line AiAk. O_ik_2 checks P2 relative to line AiAk.
    long long O_ik_1 = orient(Ai, Ak, P1);
    long long O_ik_2 = orient(Ai, Ak, P2);

    // Condition 1: The line segment P1P2 must cross the line AiAk.
    // This happens if P1 and P2 lie on strictly opposite sides of the line AiAk.
    // Since the problem states no three points are collinear, orientations O_ik_1 and O_ik_2 will be non-zero.
    // Check if their signs are different.
    bool cond1;
    if ((O_ik_1 > 0 && O_ik_2 < 0) || (O_ik_1 < 0 && O_ik_2 > 0)) {
        cond1 = true;
    } else {
        // If signs are the same, P1 and P2 are on the same side, so segment P1P2 does not cross line AiAk.
        cond1 = false;
    }

    // If Condition 1 is false, the ray cannot intersect the segment.
    if (!cond1) {
        return false;
    }

    // Condition 2: The intersection point must lie on the ray starting from Ai and passing through Ak.
    // This involves checking the positions of Ai and Ak relative to the line containing the segment P1P2.
    // Let O_12_i be orientation of Ai relative to line P1P2.
    // Let O_12_k be orientation of Ak relative to line P1P2.
    long long O_12_i = orient(P1, P2, Ai);
    long long O_12_k = orient(P1, P2, Ak);
    
    // The condition for the intersection point being on the ray Ai -> Ak is mathematically equivalent to:
    // O_12_i * (O_12_i - O_12_k) >= 0.
    // Since no three points are collinear, Ai and Ak cannot be on the line P1P2, so O_12_i != 0.
    // Also, the lines AiAk and P1P2 are not parallel, so O_12_i - O_12_k != 0.
    // Therefore, the condition simplifies to O_12_i * (O_12_i - O_12_k) > 0.
    bool cond2;
    // Calculate the difference O_12_i - O_12_k. This is safe within long long range.
    long long diff = O_12_i - O_12_k; 
    
    // Check if O_12_i and the difference 'diff' have the same sign.
    if ((O_12_i > 0 && diff > 0) || (O_12_i < 0 && diff < 0)) {
       cond2 = true;
    } else {
       cond2 = false;
    }

    // The ray intersects the segment if and only if both conditions are met.
    return cond1 && cond2;
}


int main() {
    // Use fast I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of dragons
    int M; // Number of tribes
    std::cin >> N >> M;

    std::vector<Dragon> dragons(N);
    // Store dragon indices grouped by tribe ID for efficient access later.
    // dragons_by_tribe[t] will contain a list of indices i such that dragons[i].tribe == t.
    std::vector<std::vector<int>> dragons_by_tribe(M + 1); 
    for (int i = 0; i < N; ++i) {
        // Read dragon's position (x, y) and tribe ID
        std::cin >> dragons[i].p.x >> dragons[i].p.y >> dragons[i].tribe;
        // Add the index 'i' to the list for its tribe
        dragons_by_tribe[dragons[i].tribe].push_back(i);
    }

    Point P1, P2; // Coordinates of the two villages defining the road segment P1P2
    std::cin >> P1.x >> P1.y >> P2.x >> P2.y;

    int Q; // Number of conflict queries
    std::cin >> Q;

    // Process each query one by one
    for (int j = 0; j < Q; ++j) {
        int F, G; // Tribe F becomes hostile to tribe G
        std::cin >> F >> G;

        // Initialize count of intersecting fireballs for this query
        long long count = 0; // Use long long as the count could potentially exceed 32-bit integer max (up to N^2)
        
        // Retrieve the lists of dragon indices for tribes F and G
        const auto& tribe_F_indices = dragons_by_tribe[F];
        const auto& tribe_G_indices = dragons_by_tribe[G];

        // Proceed only if both tribes involved in the conflict actually have dragons
        if (!tribe_F_indices.empty() && !tribe_G_indices.empty()) {
             // Iterate through every dragon 'i' in tribe F (the attacking tribe)
             for (int idx_i : tribe_F_indices) {
                 // Iterate through every dragon 'k' in tribe G (the target tribe)
                 for (int idx_k : tribe_G_indices) {
                      // Since F != G is guaranteed for any query, dragons idx_i and idx_k belong to different tribes.
                      // Thus, they must be distinct dragons (idx_i != idx_k implicitly).
                      
                      // Check if the fireball ray launched from dragon i towards dragon k intersects the road segment P1P2
                      if (check_intersection(dragons[idx_i].p, dragons[idx_k].p, P1, P2)) {
                          // If it intersects, increment the counter
                          count++;
                      }
                 }
             }
        }
        // Output the total count of intersecting fireballs for the current query
        std::cout << count << "\n";
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40