HDU 4380 预处理枚举

简介:

题意:给出n个房子m个矿问从n个房子选三个组成的三角形内部矿数为奇数有多少种选法。

先预处理一下每条线段正上方有多少个点,然后在枚举三条线段就可以了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
    long long x,y;
};
int cmp(point a,point b)
{
    return a.x<b.x;
}
long long Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
long long yl[205][205];
point data[205],mine[1005];
int main()
{
    int t,n,m,ca=0;
    while(~scanf("%d%d",&n,&m))
    {
        memset(yl,0,sizeof(yl));
        for(int i=0; i<n; i++)
            scanf("%I64d%I64d",&data[i].x,&data[i].y);
        for(int i=0; i<m; i++)
            scanf("%I64d%I64d",&mine[i].x,&mine[i].y);
        sort(mine,mine+m,cmp);
        sort(data,data+n,cmp);
        for(int i=0; i<n; i++)       //预处理
            for(int j=i+1; j<n; j++)
                for(int k=0; k<m&&mine[k].x<data[j].x; k++)
                    if(mine[k].x>=data[i].x&&Direction(data[i],data[j],mine[k])>0)
                        yl[i][j]++;
        long long ans=0;
        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                for(int k=j+1; k<n; k++)
                {
                    long long q=yl[i][k]-yl[i][j]-yl[j][k];
                    if(q<0) q=-q;
                    if(q%2)
                        ans++;
                }
        printf("Case %d: ",++ca);
        printf("%I64d\n",ans);
    }
    return 0;
}


目录
相关文章
|
6月前
|
存储 算法
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
LeetCode刷题---75. 颜色分类(双指针,循环不变量)
|
6月前
|
C语言
c语言编程练习题:7-50 输出华氏-摄氏温度转换表
c语言编程练习题:7-50 输出华氏-摄氏温度转换表
77 0
|
1月前
经典面试题:用预处理指令#define 声明一个常数,用以表明1年中有多少秒(忽略闰年问题)
在 C 语言中,使用 `#define` 预处理指令可以为常量命名,提高代码可读性和易维护性。通过基本时间单位换算(1 年 = 365 天 × 24 小时 × 60 分钟 × 60 秒),可以计算出一年中的总秒数,并将其定义为 `SECONDS_IN_A_YEAR`。示例代码展示了如何定义和打印这一常量,最终输出一年中有 31536000 秒。
50 15
|
5月前
【洛谷 P2089】烤鸡(循环枚举)
烤鸡问题探讨了如何组合10种配料达成特定美味程度。给定正整数$n$代表美味程度,程序需列出所有使得配料总和等于$n$的方案。样例输入11对应10种配料的不同组合,输出显示了10种符合条件的方案。代码通过暴力枚举实现,AC代码展示了如何遍历所有可能的配料质量组合来找到答案。对于100%的数据,$n\leq5000$。
51 0
|
5月前
|
C++
【洛谷 P2241】统计方形(数据加强版)题解(循环枚举)
该题目是1997年普及组的一道编程题,要求计算$n\times m$棋盘中的正方形和长方形数量(不计正方形)。输入包含两正整数$n,m\leq 5000$。输出为一行,两个正整数分别表示正方形和长方形数量。示例输入`2 3`,输出`8 10`。解题思路是将矩形数拆分为正方形数和长方形数,然后通过双重循环计算。AC代码使用C++编写,通过累加方法得出结果。
47 0
|
5月前
|
移动开发 C++
【洛谷 P1157】组合的输出 题解(深度优先搜索+枚举子集)
该问题要求编程输出从1到n中选择r个元素的所有组合,组合按字典序排列。输入包含两自然数n和r(1&lt;n&lt;21, 0≤r≤n)。输出每个组合时,每个数字占据3个字符宽度。提供的AC代码使用C++,通过递归搜索方法枚举子集。样例输入为5 3,输出显示所有3个元素的组合。
45 0
|
6月前
【错题集-编程题】体操队形(DFS + 枚举)
【错题集-编程题】体操队形(DFS + 枚举)
|
存储 算法 容器
精选算法题(1)——枚举符合要求的算术表达式(DFS、回溯法)
精选算法题(1)——枚举符合要求的算术表达式(DFS、回溯法)
蓝桥杯小技巧之巧用bit类型定义变量
蓝桥杯小技巧之巧用bit类型定义变量
81 0
|
大数据 网络安全 数据安全/隐私保护
考点:枚举法解数学题,按照条件来限定枚举结果【Python习题11】
考点:枚举法解数学题,按照条件来限定枚举结果【Python习题11】
146 0