codeworrior's blog

spoj poster
By codeworrior, 14 years ago, In English
i m doing this problem on spoj..i cant find any approach fr this..bt i feel this is to be done by sweep lines...hw to do this prob using sweep lines or by any other method??
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You can first compress coordinates and then use interval trees to determine if a poster is visible going from the last poster to the first one.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think it's also possible with sorting and sweeping.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I solved with just STL set
    → Reply
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how did you do it with set ? can you please give me your code and idea.

      this is my code.but its getting WA :(

      #include<bits/stdc++.h>
using namespace std;
int ks,kase,n,seen;
pair<int,int>pos[40010];
set<int>S;
int main()
{
    scanf("%d",&kase);
    for(ks=1;ks<=kase;ks++)
    {
        scanf("%d",&n);
        S.clear();
        seen=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&pos[i].first,&pos[i].second);
            S.insert(pos[i].first);
            S.insert(pos[i].second);
        }
        set<int>::iterator it,jt;
        for(int i=n-1;i>=0;i--)
        {
            it=S.lower_bound(pos[i].first);
            jt=S.lower_bound(pos[i].second);
            if(it!=jt )
            {
                seen++;
                S.erase(it,jt);
            }
        }
        printf("%d\n",seen);
    }
}
      → Reply