Submission #594865

#	Time	Username	Problem	Language	Result	Execution time	Memory
594865		Cross_Ratio	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	3793 ms	4496 KiB

dragon2

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
int X[30005];
int Y[30005];
int C[50005];
int X1, Y1, X2, Y2;
vector<vector<int>> Color;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=0;i<N;i++) cin >> X[i] >> Y[i] >> C[i];
    cin >> X1 >> Y1 >> X2 >> Y2;
    X2 -= X1;
    Y2 -= Y1;
    for(i=0;i<N;i++) {
        X[i] -= X1;
        Y[i] -= Y1;
        C[i]--;
    }
    X1 = Y1 = 0;
    if(X2<0) {
        X2 *= -1;
        for(i=0;i<N;i++) X[i] *= -1;
    }
    if(Y2<0) {
        Y2 *= -1;
        for(i=0;i<N;i++) Y[i] *= -1;
    }
    for(i=0;i<N;i++) {
        int x = Y2*X[i] - X2*Y[i];
        int y = X2*X[i] + Y2*Y[i];
        X[i] = x;
        Y[i] = y;
    }
    Y2 = X2*X2+Y2*Y2;
    X2 = 0;
    Color.resize(M);
    for(i=0;i<N;i++) Color[C[i]].push_back(i);
    int Q;
    cin >> Q;
    while(Q--) {
        int F, G;
        cin >> F >> G;
        F--;
        G--;
        int ans = 0;
        for(i=0;i<Color[F].size();i++) {
            for(j=0;j<Color[G].size();j++) {
                int l = Color[F][i];
                int r = Color[G][j];
                if(X[l]>0&&X[r]>0&&X[l]<=X[r]) continue;
                if(X[l]<0&&X[r]<0&&X[r]<=X[l]) continue;
                if(X[l]>X[r]) swap(l, r);
                __int128 c = -1 * (__int128)X[l]*Y[r] + (__int128)X[r] * Y[l];
                __int128 c2 = (__int128)(X[r]-X[l]) * Y2;
                if(c >= 0&& c <= c2) ans++;

            }
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:53:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(i=0;i<Color[F].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~
dragon2.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(j=0;j<Color[G].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~

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