P3260 [JLOI2014]镜面通道

    • 59通过
    • 235提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 哈希,HASH 深度优先搜索,DFS 素数判断,质数,筛法 2014 吉林 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在一个二维平面上,有一个镜面通道,由镜面AC,BD组成,AC,BD长度相等,且都平行于x轴,B位于(0,0)。

    通道中有n个外表面为镜面的光学元件,光学元件α为圆形,光学元件β为矩形(这些元件可以与其他元件和通道有交集,具体看下图)。光线可以在AB上任一点以任意角度射入通道,光线不会发生削弱。当出现元件与元件,元件和通道刚好接触的情况视为光线无法透过(比如两圆相切)。

    现在给出通道中所有元件的信息(α元件包括圆心坐标和半径xi,yi,ri,β元件包括左下角和右上角坐标x1,y1,x2,y2)

    如上图,S到T便是一条合法线路。

    当然,显然存在光线无法透过的情况,现在交给你一个艰巨的任务,请求出至少拿走多少个光学元件后,存在一条光线线路可以从CD射出。

    下面举例说明:

    现在假设,取走中间那个矩形,那么就可以构造出一条穿过通道的光路,如图中的S到T。

    输入输出格式

    输入格式:

    第一行包含两个整数,x,y,表示C点坐标第二行包含一个数字,n,表示有n个光学元件

    接下来n行第一个数字如果是1,表示元件α,后面会有三个整数xi,yi,ri分别表示圆心坐标和半径第一个数字如果是2,表示元件β,后面会有四个整数x1,y1,x2,y2分别表示左下角和右上角坐标(矩形都平行,垂直于坐标轴)

    输出格式:

    输出包含一行,至少需要拿走的光学元件个数m

    输入输出样例

    输入样例#1: 复制
    1000 100
    
    6
    
    1 500 0 50
    
    2 10 10 20 100
    
    2 100 10 200 100
    
    2 300 10 400 100
    
    2 500 10 600 100
    
    2 700 0 800 100
    输出样例#1: 复制
    2

    说明

    x<=100000,y<=1000,n<=300

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。