本文主要是介绍炫酷划线,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【题目描述】
平面上有一个圆,圆环上按顺时针顺序分布着从1到n,一共n个点。
现在无聊的小希开始按某种顺序对其在圆内两两连线,小希尽量避免让两条线碰撞,可是有的时候,这显然避免不了。
现在你知道小希划线的顺序是什么,请你判断小希在最优情况下,什么时候会被迫使得线相交,输出最早的时刻(是第几条线)
【输入描述】
数据第一行一个整数T,表示数据组数。
每组数据第一行输入两个整数N,M,代表点的个数和游戏进行的轮数。
随后M行,每行两个整数ai,bi,表示两个点之间连线。
数据保证每个点最多被连线一次。
T≤10
1≤N,M≤100000
1≤ai,bi≤100000【输出描述】
对于每组数据,一行。
如果中途某一条线开始无法避免相交,则输出当轮轮数。
否则,输出-1。
【样例】
示例1
输入
2
10 4
5 3
1 9
2 6
7 10
4 2
1 2
3 4
输出
4
-1
思路:
轮数可以用二分,枚举每一轮去判断当前轮是否有两点相交,而两点是否相交可借助栈来实现,首先预处理点,然后将点入栈,不断的读取栈中元素与所有点,判断是否相交,
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define INF 0x3f3f3f3f
#define N 100001
#define LL long long
const int MOD=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
using namespace std;int n,m;
int x[N],y[N];
int vis[N];
bool judge(int num){//当前轮数memset(vis,0,sizeof(vis));stack<int> S;for(int i=0;i<num;i++){//预处理vis[x[i]]=x[i];vis[y[i]]=-x[i];}for(int i=0;i<n;i++){//枚举所有点if(vis[i]>0)//若点是始点,进栈S.push(vis[i]);else if(vis[i]<0){//若点是终点int temp=S.top();if(temp==-vis[i])//栈顶元素与当前元素是一个点,未相交S.pop();//出栈elsereturn false;}}return true;
}
int main(){int t;cin>>t;while(t--){cin>>n>>m;for(int i=0;i<m;i++){cin>>x[i]>>y[i];if(x[i]>y[i])//保证大点在前swap(x[i],y[i]);}//对游戏轮数进行二分int left=1,right=m;while(left<=right){int mid=(left+right)/2;if(judge(mid))left=mid+1;elseright=mid-1;}if(left>m)cout<<-1<<endl;elsecout<<left<<endl;}return 0;
}
这篇关于炫酷划线的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!