首页 > 其他分享 >3.14 circle

3.14 circle

时间:2022-09-25 20:44:24浏览次数:48  
标签:输出 NO 线段 示例 3.14 相交 circle YES

★实验任务
最近 silchen又发现了一个关于圆的有趣的问题:在圆上有 2n 个不同的点,按顺序排列,n=2的时候如图:
silchen用 m 条线段把这些点连接了起来(每个点保证只连一条线段),现在他想知道这样的连接这些线段是否相交,如果不相交输出“YES”,相交输出“NO”。

★数据输入
第一行一个整数 T(1<=T<=10),接下来 T 组数据,每组数据如下
第一行一个正整数 n(1<=n<=100000)和 m(1<=m<=n)。
接下来 m 行,每行两个正整数 x 和 y,表示线段的两个端点编号。
1<=x,y<=2*n,保证每个端点只会出现一次
对于 60%的数据:1<=m<=n<=1000
对于 100%的数据:1<=m<=n<=100000

★数据输出
对每组数据输出一行,如果不相交输出“YES”,相交输出“NO”。

输入示例
4
2 2
1 2
3 4
2 2
1 3
2 4
3 3
1 6
5 2
4 3
3 3
1 4
2 6
3 5
输出示例
YES
NO
YES
NO

标签:输出,NO,线段,示例,3.14,相交,circle,YES
From: https://www.cnblogs.com/link-way/p/16728815.html

相关文章

  • [P3445] [POI2006] TAN - Dancing in Circles
    神仙题目!!!感谢程老师完成了几乎所有的证明过程。首先注意到模数是\(2005\),去掉模数似乎很不可做,所以大胆猜测正解依赖模数。不难发现,把\(n\)个人分成\(k_1\)个大小为......
  • 用Alpine 3.14镜像docker build 时出现make: /bin/sh: Operation not permitted 问题
    docker构建镜像时发现了如下的问题,翻了翻github,原因是docker版本低了/usr/src/lua-5.1.5#makelinuxcdsrc&&makelinuxmake:/bin/sh:Operationnotpermittedma......
  • HTTP 错误 403.14 - Forbidden
    1、很多人看到403.14就认为是禁止访问,因为在Web服务器上已拒绝目录列表一般情况站点都是不会允许直接读取目录内容的,如果您的站点目录没有有效的默认文档(例如index.ht......
  • 2022牛客暑假多校01B[Spirit Circle Observation]
    2022牛客暑假多校01B[SpiritCircleObservation]大致题意给出一个长度为\(n\)的字符串\(s\),求有多少个子串对\((A,B)\),满足\(1.|A|=|B|\)\(2.\overline{A}+1=......
  • Calling Circles UVA - 247
    原题链接思路把最短路换成是否可达即可代码#include<iostream>#include<cstdio>#include<cstring>#include<unordered_map>#include<vector>usingnamespace......