이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
#define double long double
#define acos acosl
#define hypot hypotl
const int maxn = 1e5+5;
struct pt{
ll x, y;
pt operator - (pt oth) {
return {x-oth.x, y-oth.y};
}
ll operator * (pt oth) {
return x * (ll) oth.x + y * (ll) oth.y;
}
ll operator ^ (pt oth) {
return x * (ll) oth.y - y * (ll) oth.x;
}
};
struct Dg{
pt p;
double A, B;
bool above;
};
double getang(pt v, pt u) {
// from v to u, clockwise
return ((v*u) / (hypot(v.x, v.y) * hypot(u.x, u.y)));
}
const double PI = acos(-1);
vector<Dg> G[maxn];
signed main(){
int n,m; cin>>n>>m;
for(int i = 0; i<n; ++i) {
int a,b,c; cin>>a>>b>>c;
G[c].pb({{a,b},0,0});
}
pt S, T; cin>>S.x>>S.y>>T.x>>T.y;
for (int i = 1; i<=m; ++i) {
for (Dg & d : G[i]) {
d.A = getang(d.p-S, T-S);
d.B = getang(d.p-T, S-T);
bug(d.p.x, d.p.y);
bug(d.A, d.B);
d.above = ((T-S) ^ (d.p - S)) > 0;
bug(d.above);
}
}
int Q; cin>>Q;
while (Q--) {
int a,b; cin>>a>>b;
int ret = 0;
for (Dg &d1 : G[a]) {
for (Dg & d2 : G[b]) {
if (d1.above == d2.above) {
ret += ((((d1.p-S)^(d2.p-S))>0) != ((((d1.p-T)^(d2.p-T))) > 0)) && ((((T-S) ^ (d2.p-S)) > 0) == (((d2.p-S) ^ (d1.p-S)) > 0));
}else{
ret += ((((d1.p-S)^(d2.p-S))>0) != ((((d1.p-T)^(d2.p-T))) > 0));
}
}
}
cout<<ret<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |