#include "bits/stdc++.h"
using namespace std;
#define ar array
//~ typedef long long ll;
//~ #define int ll
typedef double ll;
const double pi = acos(-1);
const double eps = 1e-9;
struct vec_t{
ll x, y;
void rd(){
cin >> x >> y;
}
vec_t(): vec_t(0, 0) {};
vec_t(ll x, ll y): x(x), y(y) {};
//~ vec operator / (const double& d) const{
//~ return {x / d, y / d};
//~ };
bool operator < (const vec_t& b) const {
if(x != b.x) return x < b.x;
return y < b.y;
}
vec_t operator - (const vec_t& b) const{ return {x - b.x, y - b.y}; }
vec_t operator + (const vec_t& b) const{ return {x + b.x, y + b.y}; }
ll operator * (const vec_t& b) const{ return x * 1ll * b.x + y * 1ll * b.y; }
ll operator % (const vec_t& b) const{ return x * 1ll * b.y - y * 1ll * b.x; }
double len() const { return sqrt(x * 1ll * x + y * 1ll * y); }
ll len2() const { return x * 1ll * x + y * 1ll * y; }
};
struct line_t{
ll a, b, c;
void rd(){
cin >> a >> b >> c;
}
line_t(): line_t(0, 0, 0) {}
line_t(const ll& a, const ll& b, const ll& c): a(a), b(b), c(c) {}
line_t(const vec_t& p1, const vec_t& p2){
a = p2.y - p1.y;
b = p1.x - p2.x;
c = -(a * p1.x + b * p1.y);
}
double dis(const vec_t& p){
vec_t n(a, b);
return (p * n + c) / n.len();
}
ar<ll, 3> intersect(const line_t& x){
return {vec_t(-c, b) % vec_t(-x.c, x.b),
vec_t(a, -c) % vec_t(x.a, -x.c),
vec_t(a, b) % vec_t(x.a, x.b)};
}
};
struct seg_t{
vec_t a, b;
line_t L;
void rd(){
a.rd(), b.rd();
L = line_t(a, b);
}
seg_t(): seg_t(vec_t(), vec_t()) {}
seg_t(const vec_t& a, const vec_t& b): a(a), b(b) {
L = line_t(a, b);
}
bool is_in(const vec_t& p){
return abs((a - p) % (b - p)) < eps && min((p - a) * (b - a), (p - b) * (a - b)) + eps > 0;
}
double dis(const vec_t& p){
if((p - a) * (b - a) - eps < 0 || (p - b) * (a - b) - eps < 0){
return min((p - a).len(), (p - b).len());
} else {
return abs(L.dis(p));
}
}
double dis(seg_t seg){
ar<ll, 3> P = L.intersect(seg.L);
if(P[2]){
vec_t p(P[0] * 1. / P[2], P[1] * 1. / P[2]);
if(is_in(p) && seg.is_in(p)){
return 0;
}
}
return min({seg.dis(a), seg.dis(b), dis(seg.a), dis(seg.b)});
}
};
struct ray_t{
vec_t a, b;
line_t L;
void rd(){
a.rd(), b.rd();
L = line_t(a, b);
}
ray_t(): ray_t(vec_t(), vec_t()) {}
ray_t(const vec_t& a, const vec_t& b): a(a), b(b) {
L = line_t(a, b);
}
bool is_in(const vec_t& p){
return abs((a - p) % (b - p)) < eps && (p - a) * (b - a) + eps > 0;
}
double dis(const vec_t& p){
if((p - a) * (b - a) - eps < 0){
return (p - a).len();
} else {
return abs(L.dis(p));
}
}
bool dis(seg_t seg){
ar<ll, 3> P = L.intersect(seg.L);
if(P[2]){
vec_t p(P[0] * 1. / P[2], P[1] * 1. / P[2]);
if(is_in(p) && seg.is_in(p)){
return true;
}
}
return false;
//~ return min({seg.dis(a), dis(seg.a)});
}
};
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
vector<vec_t> p(n);
vector<int> c(n);
vector<vector<int>> res(m, vector<int>(m));
for(int i=0;i<n;i++){
p[i].rd();
cin >> c[i]; c[i]--;
}
vec_t p1, p2; p1.rd(), p2.rd();
seg_t S(p1, p2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(c[i] == c[j]) continue;
if(ray_t(p[i], p[j]).dis(S)){
res[c[i]][c[j]]++;
}
}
}
int q; cin >> q;
while(q--){
int a, b; cin >> a >> b;
a--, b--;
cout<<res[a][b]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4045 ms |
1540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
