hdu 1756 Cupid's Arrow 计算几何

    判断点是否在多边形内部

    对于任意四边形,可以随机选取一条射线向外延伸,如果相交边数为奇数,则在内,偶数,则在外

   这题无需考虑在边上的情况

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
给定n个点的坐标,这n个点依次围成一闭合多边形,再给一点(x,y),判断它是否在多边形中。
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
#define eps 1e-8
using namespace std;
struct Node
{
    double x,y;
};
Node org[1000005];
Node A,B;
int n,i;
double cross(Node A, Node B, Node C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
bool isZero(double x) {//判断x是否接近0
    return (x > 0 ? x : -x) < eps;
}
bool in()
{
    int count, i = 0;
    org[n] = org[0];
    while (i < n)
    {
        B.x = rand() + INF;  //随机取一个足够远的点B
        B.y = rand() + INF;  //以A为起点B为终点做射线L
        for (i=count=0; i<n; ++i)
        {
           /*
            if (isZero(cross(A,org[i],org[i+1]))&&
              (org[i].x-A.x)*(org[i+1].x-A.x)<eps&&(org[i].y-A.y)*(org[i+1].y-A.y)<eps)
                return 0;//点A在边上
           */
            if (isZero(cross(A, B, org[i]))) break;//点org[i]在射线AB上,停止本循环,另取B
            else if (cross(org[i], org[i+1], A)*cross(org[i], B, org[i+1])>eps &&//射线与边相交,统计交点数
                     cross(A, B, org[i])*cross(A, org[i+1], B)>eps)  ++count;
        }
    }
    return count & 1;
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&org[i].x,&org[i].y);
        }
        int m;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%lf%lf",&A.x,&A.y);
            if(in())puts("Yes");
            else puts("No");
        }
    }
}
时间: 2024-05-16 05:09:00

hdu 1756 Cupid&#39;s Arrow 计算几何的相关文章

【HDU 4738 Caocao&amp;#39;s Bridges】BCC 找桥

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4738 题意:给定一个n个节点m条边的无向图(可能不连通.有重边),每条边有一个权值.判断其连通性,若双连通,输出-1:若非连通,输出0:否则,输出权值最小的桥的权值. 思路:进行双连通域分解,记下连通块的个数和所有桥的情况,对应输出结果即可. 注意对重边的处理.这里我按照上一道题学到的姿势如法炮制:先把所有边按"字典序"排序(u, v, w),这样重边聚集在一起了,然后扫描一遍,发现重边即

hdu 5280 Senior&amp;#39;s Array

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5280 问题描述 某天学姐姐得到了一个数组A ,在这个数组的所有非空区间中,她找出了一个区间和最大的,并把这个区间和定义为这个数组的美丽值. 但是她觉得这个数组不够美,于是决定修理一下这个数组. 学姐姐将会进行一次操作,把原数组中的某个数修改为P (必须修改). 最后她想使得修改后的数组尽可能美丽.请你帮助她计算经过修理后,这个数组的美丽值最大能是多少? #include <iostream> #i

HDU 1558:Segment set, 计算几何+并查集

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1558 题目类型: 计算集合 , 并查集 题目: A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some

hdu 5281 Senior&amp;#39;s Gun

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5281 题目大意:学姐姐是一个酷酷的枪手. 她常常会随身携带n 把枪,每把枪有一个攻击力a[i] . 有一天她遇到了m 只怪兽,每只怪兽有一个防御力b[j] .现在她决定用手中的枪消灭这些怪兽. 学姐姐可以用第i 把枪消灭第j 只怪兽当且仅当b[j]≤a[i] ,同时她会获得a[i]−b[j] 的分数. 每把枪至多只能使用一次,怪兽死后也不会复活.现在学姐姐想知道她最多能得到多少分(她可以不用消灭所有

hdu 5334 MZL&amp;#39;s xor

hdu 5334 的传送门 MZL loves xor very much.Now he gets an array A.The length of A is n.He wants to know the xor of all (Ai+Aj)(1≤i,j≤n) The xor of an array B is defined as B1 xor B2-xor Bn Input Multiple test cases, the first line contains an integer T(no

hdu 5349 MZL&amp;#39;s simple problem

hdu 5349 的传送门 Problem Description A simple problem Problem Description You have a multiple set,and now there are three kinds of operations: 1 x : add number x to set 2 : delete the minimum number (if the set is empty now,then ignore it) 3 : query the

hdu 1250 Hat&amp;#39;s Fibonacci

点击此处即可传送hdu 1250 Problem Description A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1. F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4) Your

hdu 2147 kiki&amp;#39;s game

http://acm.hdu.edu.cn/showproblem.php?pid=2147 这是一个巴什博弈的题,当两个数至少有一个数是偶数先手必胜 代码如下: #include <iostream> #include <cstdio> using namespace std; int main() { int m,n; while(cin>>m>>n,m,n) { if(m%2 && n%2) puts("What a pity

hdu 3509 Buge&amp;#39;s Fibonacci Number Problem

点击此处即可传送 hdu 3509 题目大意:F1 = f1, F2 = f2;; F(n) = a*F(n-1) + b*F(n-2); S(n) = F1^k + F2^k +-.+Fn^k; 求S(n) mod m; 解题思路: 1:首先一个难题就是怎么判断矩阵的维数(矩阵的维数是个变量) 解决方法:开一个比较大的数组,然后再用一个公有变量记一下就行了,具体详见代码: 2:k次方,找规律: 具体上代码吧: /* 2015 - 8 - 16 晚上 Author: ITAK 今日的我要超越昨日