Submission #369180

#	Time	Username	Problem	Language	Result	Execution time	Memory
369180		denkendoemeer	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4034 ms	6640 KiB

dragon2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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;
    scanf("%d%d",&n,&m);
    int i;
    for(i=0;i<n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[c].push_back({{a,b},0,0});
    }
    pct s,t;
    scanf("%lld%lld%lld%lld",&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;
    scanf("%d",&q);
    for(i=1;i<=q;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        int ans=0;
        for(aux &it1:g[a]){
            for(aux &it2:g[b]){
                if (it1.ok==it2.ok){
                    if ((((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))
                        ans++;
                }
                else{
                    if ((((it1.p-s)^(it2.p-s))>0)!=(((it1.p-t)^(it2.p-t))>0))
                        ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%lld%lld%lld%lld",&s.x,&s.y,&t.x,&t.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
dragon2.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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