Angle Beats Gym

Stella981
• 阅读 639

Angle Beats

$$ Time Limit: 4000 ms \quad Memory Limit: 1048576 kB $$

题意

给出 $n$ 个初始点以及 $q$ 次询问,每次询问给出一个询问点 $Q$,求包括 $Q$ 点的直角三角形有多少个。保证 $n+q$ 个点都不重复。

思路

  1. 对于每次询问,当 $Q$ 为直角点时,以 $Q$ 为原点,对 $n$ 个点做象限极角排序,然后用双指针 $L$、 $R$ 维护直角三角形的个数。 $L$ 指针用来枚举其中的一条直角边, $R$ 指针用来寻找在另一条直角边上的点有多少个,每次找 $QL$ 这条边逆时针方向的另一条边$QR$。所以当 $L$ 往逆时针转动时,$R$ 也会往逆时针转动,那么就可以用双指针直接维护出来了,特别注意一下多个点在同一条直线上的情况就可以了。
  2. 若 $Q$ 不是直角点时,可以离线处理,把 $n+q$ 个点全部存出来,然后枚举以 $n$ 个初始点为直角点时,对哪些的 $Q$ 点有贡献,维护方法同上。

最后的复杂度为 $O\left(qnC_1 + n(n+q)C_2\right)$,$C_1、C_2$ 取决于在枚举直角点为原点后,到原点在同一条直线上的点数量。 我试过把 $n+q$ 个节点全部提取出来,然后暴力枚举每个点为直角点的情况,但是这样复杂度会 $T$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e4+10;

struct Point {
    ll x, y;
    int id;
} p[maxn], be[maxn];
int n, m;
int ans[maxn];

int cmp1(Point a, Point b) {
    ll d = a.x*b.y - b.x*a.y;
    if(d == 0) {
        return a.x<b.x;
    } else {
        return d>0;
    }
}
int Qua(Point a) {
    if(a.x>0 && a.y>=0)    return 1;
    if(a.x<=0 && a.y>0)    return 2;
    if(a.x<0 && a.y<=0)    return 3;
    if(a.x>=0 && a.y<0)    return 4;
}

int cmp(Point a, Point b) {
    if(Qua(a) == Qua(b))    return cmp1(a, b);
    else    return Qua(a)<Qua(b);
}

ll check(Point a, Point b) {
    return a.x*b.x + a.y*b.y;
}

ll chaji(Point a, Point b) {
    return a.x*b.y - b.x*a.y;
}

ll work(Point pp) {
    for(int i=1; i<=n; i++) {
        p[i] = be[i];
        p[i].x -= pp.x;
        p[i].y -= pp.y;
    }
    p[0] = pp;
    sort(p+1, p+1+n, cmp);
    for(int j=1; j<=n; j++) {
        p[j+n] = p[j];
    }
    ll ans = 0;
    int R = 2;
    for(int L=1; L<=n; L++) {
        while(R<=2*n) {
            if(chaji(p[L], p[R]) < 0)    break;
            if(check(p[L], p[R]) <= 0)    break;
            R++;
        }
        int tR = R;
        while(tR<=2*n) {
            if(chaji(p[L], p[tR]) <= 0)    break;
            if(check(p[L], p[tR]) != 0)    break;
            ans++;
            tR++;
        }
    }
    return ans;
}

int main(){
    // freopen("in", "r", stdin);
    while(~scanf("%d%d", &n, &m)) {
        int all = 0;
        for(int i=1; i<=n; i++) {
            all++;
            int x, y;
            scanf("%d%d", &x, &y);
            p[all].x = x, p[all].y = y, p[all].id = 0;
            be[all] = p[all];
        }
        for(int i=1; i<=m; i++) {
            all++;
            int x, y;
            scanf("%d%d", &x, &y);
            p[all].x = x, p[all].y = y, p[all].id = i;
            be[all] = p[all];
            ans[i] = work(p[all]);
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=all; j++) {
                p[j] = be[j];
            }
            p[0] = be[i];
            int flag = 0;
            for(int j=1; j<=all; j++) {
                if(p[j].x == p[0].x && p[j].y == p[0].y)    flag = 1;
                if(flag)    p[j] = p[j+1];
                p[j].x -= p[0].x;
                p[j].y -= p[0].y;
            }

            int nn = all-1;
            sort(p+1, p+1+nn, cmp);
            for(int j=1; j<=nn; j++) {
                p[j+nn] = p[j];
            }
            int R = 2;
            for(int L=1; L<=nn; L++) {
                int id = 0;
                if(p[0].id)    id = p[0].id;
                if(p[L].id)    id = p[L].id;
                while(R<=2*nn) {
                    if(chaji(p[L], p[R]) < 0)    break;
                    if(check(p[L], p[R]) <= 0)    break;
                    R++;
                }
                int tR = R;
                while(tR<=2*nn) {
                    if(chaji(p[L], p[tR]) <= 0)    break;
                    if(check(p[L], p[tR]) != 0)    break;
                    if(id == 0)    {
                        if(p[tR].id)    ans[p[tR].id]++;
                    } else {
                        if(p[tR].id == 0)    ans[id]++;
                    }
                    tR++;
                }
            }
        }
        for(int i=1; i<=m; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}
点赞
收藏
评论区
推荐文章
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Souleigh ✨ Souleigh ✨
3年前
前端性能优化 - 雅虎军规
无论是在工作中,还是在面试中,web前端性能的优化都是很重要的,那么我们进行优化需要从哪些方面入手呢?可以遵循雅虎的前端优化35条军规,这样对于优化有一个比较清晰的方向.35条军规1.尽量减少HTTP请求个数——须权衡2.使用CDN(内容分发网络)3.为文件头指定Expires或CacheControl,使内容具有缓存性。4.避免空的
DaLongggggg DaLongggggg
3年前
python-算法训练 区间k大数查询
问题描述给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n,表示序列长度。第二行包含n个正整数,表示给定的序列。第三个包含一个正整数m,表示询问个数。接下来m行,每行三个数l,r,K,表示询问序列从左往右第l个数到第r个数中,从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行,每行一个数
Easter79 Easter79
3年前
sql 查询
高效SELECTq.ID\_ANSWER,q.ID\_QUESTION,q.CONTENT,q.UPVOTE\_TOTE,q.IS\_ADOPT,q.ID\_USER,q.OPPOSE\_TOTE,q.ANSWER\_TIME,q.ACT\_FLAG,q.SCORE,u.OFFICIAL\_EXPERT,qs.TITLE,qs.I
Stella981 Stella981
3年前
Codeforces 862B (二分图染色)
<题目链接(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fvjudge.net%2Fproblem%2FCodeForces862B)\题目大意:给出一个有n个点的二分图和n1条边,问现在最多可以添加多少条边使得这个图中不存在自环,重边,并且此图还是一个二
Stella981 Stella981
3年前
HDU 3416 Marriage Match IV (Dijkstra+最大流)
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的ST的最短路有多少条。分析:首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢?可以这样:先对起点S,跑出最短路;对于每条边e(u,v,w),若d\u\wd\v\。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两
Stella981 Stella981
3年前
Dubbo爆出严重漏洞!可导致网站被控制、数据泄露!附解决方案
http://dy.163.com/v2/article/detail/F5FPIFRU0511Q1AF.html  !(http://dingyue.ws.126.net/2020/0216/125ec4c4p00q5rcrs0019d200ig009qg00ig009q.png)  来源:华为云  原文地址:https://w
Stella981 Stella981
3年前
Seeker的奇妙求职历险(网易互联网笔试)
素数的个数给出一个包含n个正整数的数组a,把a\i\拆分为若干个和为a\i\的素数,求拆分后最多能有多少个素数。第一行数据为n,表示数组长度,第二行为n个元素。输入3111输出01不可拆分输入135761为0个,3为1个,5为(2,3
Stella981 Stella981
3年前
AC(Aho—Corasiek) 多模式匹配算法
简介:AC多模式匹配算法产生于1975年的贝尔实验室,最早使用于图书馆的书目查询程序中。该算法以有限状态自动机(FSA),以及KMP前缀算法为基础.(有说法:ac自动机是KMP的多串形式,是一个有限自动机)AC定义:AC有限自动机M是1个6元组:M(Q,∑,g,f,qo,F)其中:1、Q是有
Wesley13 Wesley13
3年前
51nod 1318 最大公约数与最小公倍数方程组(2
题意给你$n$个元素,$m$个方程。每个方程形如$$\\begin{align}\\gcd(x\_i,y\_i)c\_i\\\\mathrm{lcm}(x\_i,y\_i)d\_i\\end{align}$$之类的形式。询问这个方程组是否有解。有$T$组数据。$1\\leT\\le10,1\