Форум программистов, компьютерный форум CyberForum.ru

Принадлежность точки отрезку - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
AlekseyL
0 / 0 / 0
Регистрация: 02.05.2014
Сообщений: 3
02.05.2014, 00:14     Принадлежность точки отрезку #1
Добрый день, уважаемые форумчане. Помогите пожалуйста с задачей. В первой строке задано два целых числа n и m (1≤n≤50000, 1≤m≤50000) — количество отрезков и точек на прямой, соответственно. Следующие n строк ввода содержат по два целых числа ai и bi (ai≤bi) — координаты концов отрезков. Последняя строка содержит m целых чисел — координаты точек. Все координаты не превышают 10^5 по модулю. Точка считается принадлежащей отрезку, если она находится внутри него или на границе. Для каждой точки в порядке появления во вводе выведите, скольким отрезкам она принадлежит.

Я читаю начала и концы отрезков в разные массивы, сортирую массивы и ищу в каждом количество элементов меньше заданного. Правильного ответа вроде добился, но по времени не проходит. Подозреваю что виновны 13 и 14 строки, но как переделать не знаю...
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
int binary_search(int x, int l ,int r, int*h){
    int k, mid;
    k=0;
     while(r - l > 1){
         mid = (l + r) / 2;
         if(h[mid]<=x){
             k=k-l+mid;
             l = mid;}
         else{
             r = mid;}}
           if(h[mid-1]<=x){
            k++;}
             return k;}
 
void quickSort(int l, int r, int*s)
{
     int x = s[l + (r - l) / 2];
     int i = l;
     int j = r;
     while(i <= j)
     {
         while(s[i] < x) i++;
         while(s[j] > x) j--;
         if(i <= j)
         {
             swap(s[i], s[j]);
             i++;
             j--;
         }
     }
     if (i<r)
                 quickSort(i, r, s);
     
     if (l<j)    
         quickSort(l, j, s);    
}
int main(){
    
     int n, m, k, p, i;
     cin >> n >> m;
     int a[n], b[n], c[m];
     for(i = 0; i < n; i++){
            cin>>a[i]>>b[i];}
            
     quickSort(0, n-1, a);
     quickSort(0, n-1, b);
 
     for(i = 0; i < m; i++){
        cin >> c[i];
        cout<< binary_search(c[i], 0 , n, a)-binary_search(c[i], 0 , n, b)<<" ";
     }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2014, 00:14     Принадлежность точки отрезку
Посмотрите здесь:

C++ Принадлежность точки к отрезку.
принадлежность точки к кольцу C++
принадлежность точки прямоугольнику C++
Принадлежность точки N-угольнику. C++
принадлежность точки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
4265 / 3696 / 1243
Регистрация: 14.04.2014
Сообщений: 14,479
02.05.2014, 07:40     Принадлежность точки отрезку #2
a и b сортируешь раздельно? Как потом узнаешь какому отрезку принадлежат точки, они же смешаются?
AlekseyL
0 / 0 / 0
Регистрация: 02.05.2014
Сообщений: 3
02.05.2014, 18:51  [ТС]     Принадлежность точки отрезку #3
Попробовал слить всё в один массив...Распределить ответ в нужном порядке не получается.
Превышение по времени.
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
using namespace std;
 
int BS(int*t, int x, int l, int h){
 int middle;
 while (l <= h){
 middle = (l + h) / 2;
 if (x == t[middle])
 return middle;
 else if (x < t[middle])
 h = middle - 1;
 else
 l = middle + 1;}
 return -1;}
 
void quickSort(int l, int r, int*c, int*d){
     int x = c[l + (r - l) / 2];
     int i = l;
     int j = r;
     while(i <= j){
         while(c[i] < x) i++;
         while(c[j] > x) j--;
         if(i <= j){
             swap(c[i], c[j]);
             swap(d[i], d[j]);
             i++;
             j--;}}
     if (i<r)
                 quickSort(i, r, c, d);
     if (l<j)    
         quickSort(l, j, c, d);}    
    
int main(){
int n, m, k;
cin >> n >> m;
int a[2*n+m], b[2*n+m], s[2*n+m];
int q[2*n+m];
for (int i=0; i<2*n+m; i++){
    cin >> a[i];
    q[i]=a[i];}
for (int i=0; i<2*n; i=i+2){
    b[i]=1;
    b[i+1]=-1;} 
for (int i=2*n; i<2*n+m; i++){
    b[i]=0;}
    
quickSort(0, 2*n+m-1, a, b);
    k=0;
 
for(int i=0; i<2*n+m; i++){
    k=k+b[i];
    if(b[i]==0){
        s[i]=k;}}
        
        int z=0;
for(int i=2*n; i<2*n+m; i++){
    while(b[BS(a, q[i], 0, 2*n+m)]!=0){
        z++;}
    cout << s[BS(a, q[i], z, 2*n+m)]<<" ";
        z=0;
}
}
ture
 Аватар для ture
404 / 297 / 120
Регистрация: 27.11.2014
Сообщений: 1,004
23.11.2015, 17:17     Принадлежность точки отрезку #4
Вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
#include <cmath>
 
int main() {
    //спрашиваем отрезки
    int n, k;
    std::cin >> n >> k;
    int * L = new int[n];
    int * R = new int[n];
    for(int i = 0; i < n; ++i)
        std::cin >> L[i] >> R[i];
 
    //сортируем 
    std::sort(L, L + n);
    std::sort(R, R + n);
 
    //спрашиваем точки
    for(int i = 0, x, cnt=0; i < k; ++i) {
        std::cin >> x;
        //сколько отрезков начинается левее х
        int left = 0, right = n - 1, m;
        while(left <= right) {
            m = (left + right) / 2; //середина
            if(L[m]>x)
                right = m - 1;   //справа отрезки правее точки
            else
                left  = m + 1;       
        }
        cnt = right + 1;
        //сколько отрезков кончается правее х
        left  = 0;
        right = n-1;
        while(left <= right) {
            m = (left + right) / 2; //середина
            if(R[m]<x)
                left = m + 1;   //слева отрезки закончились раньше x
            else
                right = m - 1;
        }
        cnt -= right+1;
        std::cout << cnt << " ";
        
    }
 
    delete[] L, R;
    //std::system("pause");
    return 0;
}
Yandex
Объявления
23.11.2015, 17:17     Принадлежность точки отрезку
Ответ Создать тему
Опции темы

Текущее время: 16:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru