This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<cmath>
#include<vector>
#include<iostream>
using namespace std;
#define ll long long
#define double long double
struct pct
{
ll x,y;
pct operator - (pct aux)
{
return {x-aux.x,y-aux.y};
}
ll operator * (pct aux)
{
return 1LL*x*aux.x+1LL*y*aux.y;
}
ll operator ^ (pct aux)
{
return 1LL*x*aux.y-1LL*y*aux.x;
}
};
struct aux
{
pct p;
double a,b;
bool ok;
};
double unghi(pct x,pct y)
{
return ((x*y)/(hypotl(x.x,x.y)*hypotl(y.x,y.y)));
}
const double pi=acos(-1);
vector<aux>g[100005];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int n,m;
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
int i;
for(i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
g[c].push_back({{a,b},0,0});
}
pct s,t;
cin>>s.x>>s.y>>t.x>>t.y;
for(i=1;i<=m;i++){
for(aux &it:g[i]){
it.a=unghi(it.p-s,t-s);
it.b=unghi(it.p-t,s-t);
if (((t-s)^(it.p-s))>0)
it.ok=1;
else
it.ok=0;
}
}
int q;
cin>>q;
for(i=1;i<=q;i++){
int a,b;
cin>>a>>b;
int ans=0;
for(aux &it1:g[a]){
for(aux &it2:g[b]){
if (it1.ok==it2.ok){
ans=ans+(((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0)) && ((((t-s)^(it2.p-s))>0)==(((it2.p-s)^(it1.p-s))>0)));
}
else{
ans=ans+((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0));
}
}
}
cout<<ans<<'\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |