首页 > 代码库 > CF 14B B. Young Photographer

CF 14B B. Young Photographer

2024-07-13 22:57:29   223人阅读

Among other things, Bob is keen on photography. Especially he likes to take pictures of sportsmen. That was the reason why he placed himself in position x0 of a long straight racetrack and got ready to take pictures. But the problem was that not all the runners passed him. The total amount of sportsmen, training at that racetrack, equals n. And each of them regularly runs distances within a particular segment of the racetrack, which is the same for each sportsman. For example, the first sportsman runs from position a1 to position b1, the second — from a2 to b2

What is the minimum distance that Bob should move to have a chance to take pictures of each sportsman? Bob can take a picture of a sportsman, if he stands within the segment that this sportsman covers on the racetrack.

Input

The first line of the input file contains integers n and x0 (1?≤?n?≤?100; 0?≤?x0?≤?1000). The following n lines contain pairs of integersai,?bi (0?≤?ai,?bi?≤?1000; ai?≠?bi).

Output

Output the required minimum distance in the same units as the positions on the racetrack. If there is no such a position, output -1.

Sample test(s)
input
3 3
0 7
14 2
4 6
output
1
我的做法维护区间最大值（maxn)和最小值(minn)=-=，最后还要判一下x0在不在这个区间内；
如果在，不用动，输出0，不再则输出到maxn,minn的最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,x0;
struct node{
    int a,b;
}s[110];
int cmp(node l1,node l2)
{
    return l1.a<l2.a;
}
int main()
{
    int u,v,i;
    while(cin>>n>>x0)
    {
        for(i=0;i<n;i++)
        {
            cin>>u>>v;
            if(u>v)
                swap(u,v);
            s[i].a=u;
            s[i].b=v;
        }
        sort(s,s+n,cmp);
        int maxn=s[0].b;
        int minn=s[0].a;
        for(i=1;i<n;i++)
        {
            if(s[i].b<minn)
                break;
            if(s[i].a>maxn)
                break;
            if(s[i].a>minn)
                minn=s[i].a;
            if(s[i].b<maxn)
                maxn=s[i].b;
        }
        if(i==n)
        {
            if(x0>=minn&&x0<=maxn)
                cout<<0<<endl;
            else
                cout<<min(abs(minn-x0),abs(maxn-x0))<<endl;
        }
        else
            cout<<-1<<endl;
    }
    return 0;
}



联系
我们