#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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
13268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4019 ms |
15404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
13268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
