Submission #928486

#	Time	Username	Problem	Language	Result	Execution time	Memory
928486		andrey27_sm	Dragon 2 (JOI17_dragon2)	C++17	0 / 100	4019 ms	15404 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __float128 ld;
pair<ll,ll> points[300000];
pair<ll,ll> a;
pair<ll,ll> b;
int tribe[300000];
pair<ld,ld> angles[300000];
pair<int,int> angles_sorted[300000];
pair<int,int> angles_rev[300000];
int part[300000];
ll dist_sq(pair<ll,ll> a, pair<ll,ll> b) {
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
int sign(ll x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}
ll cross(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c) {
    return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}
ll cros_mod(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c) {
    return abs(cross(a,b,c));
}

int cnt_from[3001][3001];


int main() {
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second >> tribe[i];
    }
    cin >> a.first >> a.second >> b.first >> b.second;
    ld dist_ab = dist_sq(a,b);
    vector<ld> angles_all;
    for (int i = 0; i < n; i++) {
        ll dist_ai = dist_sq(a,points[i]);
        ll dist_bi = dist_sq(b,points[i]);
        ld angle = (dist_ai+dist_ab-dist_bi);
        ld angle2 = (dist_bi+dist_ab-dist_ai);
        // angle to a
        part[i] = sign(cross(a,b,points[i]));
        ll S = cros_mod(a,b,points[i]);
        ld tmp = (S*S)/(dist_ai*dist_ab);
    
        if(angle > 0) {
            tmp-=1;
        }
        else {
            tmp = 1-tmp;
        }
        angles[i].first = tmp;
        angles_all.push_back(tmp);
        tmp = -tmp;
        angles_all.push_back(tmp);
        // angle to b
        tmp = (S*S)/(dist_bi*dist_ab);
        if(angle2 > 0) {
            tmp-=1;
        }
        else {
            tmp = 1-tmp;
        }        
        angles[i].second = tmp;
        angles_all.push_back(tmp);
        tmp = -tmp;
        angles_all.push_back(tmp);

    }
    sort(angles_all.begin(),angles_all.end());
    for (int i = 0; i < n; i++) {
        angles_sorted[i] = {lower_bound(angles_all.begin(),angles_all.end(),angles[i].first)-angles_all.begin(),lower_bound(angles_all.begin(),angles_all.end(),angles[i].second)-angles_all.begin()};
        angles_rev[i] = {lower_bound(angles_all.begin(),angles_all.end(),-angles[i].first)-angles_all.begin(),lower_bound(angles_all.begin(),angles_all.end(),-angles[i].second)-angles_all.begin()};
        // cout << i << "\n";
        // cout << (long double)angles[i].first << " " << (long double)angles[i].second << "\n";
        // cout << angles_sorted[i].first << " " << angles_sorted[i].second << "\n";
        // cout << angles_rev[i].first << " " << angles_rev[i].second << "\n";
        // cout << part[i] << "-\n";
    }
    for(int i = 0;i < n;i++) {
        pair<int,int> same_part = angles_sorted[i];
        pair<int,int> other_part = angles_rev[i];
        for (int j = 0; j < n;j++) {
            if(i == j) {
                continue;
            }
            bool hit = false;
            if(part[i] == part[j]) {
                if(angles_sorted[j].first <= same_part.first && angles_sorted[j].second <= same_part.second) {
                    hit = true;
                }
            }
            else {
                if(angles_sorted[j].first <= other_part.first && angles_sorted[j].second <= other_part.second) {
                    hit = true;
                }
            }
            if(hit) {
                // cout << i << " " << j << " " << hit << "\n";
                cnt_from[tribe[i]][tribe[j]]++;
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x,y;
        cin >> x >> y;
        cout << cnt_from[x][y] << "\n";
    }
}

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