terminated's blog

codeforces 291 problem B
By terminated, 9 years ago, In English

In Problem B of yesterdays contest I wrote this solution and got it wrong on pretest 8

int n;
        cin>>n;
        set<double> s;
        int c1=0;
        double a,b;
        cin>>a>>b;
        double result;int c=0;
        rep(i,n)
        {
            double x,y;
            cin>>x>>y;

            result = atan ((y-b)/(x-a)) * 180.0 / PI;
            if(*lower_bound(s.begin(), s.end(),result)!=result)
                   { c++;s.insert(result);}

            
        }   
        cout<<c<<"\n";

then I wrote this and got it accepted


        int n;
        cin>>n;
        set<double> s;
        int c1=0;
        double a,b;
        cin>>a>>b;
        double result;int c=0;
        rep(i,n)
        {
            double x,y;
            cin>>x>>y;

       if(x-a!=0)
            result = (y-b)/(x-a);
         else
            result=INF;

            if(*lower_bound(s.begin(), s.end(),result)!=result)
                   { c++;s.insert(result);}

            
        }   
        cout<<c<<"\n";

The only difference between the accepted and unaccepted is the "atan" thing ,,In first case I calculated it using taninverse and In second using normal slope formula,,but I am not able to figure out why the atan fails,,any explanation will help.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

One possible bug is that atan() has range [-pi/2, pi/2]. In particular atan(1/0) will return pi/2, while atan(-1/0) will return -pi/2; but for your solution to be correct, they both should correspond to the same slope.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

you are right...my code also got pretest 8 but i do not use "atan" function.

include

define INF 999999

using namespace std; double s[1001];

int main() { double x,y,x0,y0; int num=0,test,cnt=0; double slop;

cin>>test>>x0>>y0;

for(int i = 0;i < test;i++) {
    cin>>x >> y;
    if( x == x0) slop=INF;
    else {
        slop = (y0 - y)/(x0 - x);
    }
    int flag=0;
    for(int j=0;j<cnt;j++) {
        if(s[j]==slop) {
            flag=1;
            break;
        }
    }
    if(flag==0) {
        num+=1;
        s[cnt]=slop;
        cnt+=1;
    }
}
cout<<num;
return 0;

}

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

pratyaksh has already mentioned one problem in your code. And I can see two problems more.

Firstly, set has its own set<T>::lower_bound method which works in O(logn), while lower_bound works in O(n) for set:

set<T> s;
...
s.lower_bound(result) // O(log n)
lower_bound(s.begin(), s.end(), result) // O(n)

For this particular problem it's not a big deal because n ≤ 1000

And the second problem: *lower_bound(s.begin(), s.end(),result)!=result is undefined behavior. If result is bigger than anything else in the set, lower_bound will return s.end(). But result of *s.end() execution is undefined.

So it would be better to write something like s.lower_bound(result) == s.end() instead of *lower_bound(s.begin(), s.end(),result)!=result

BTW, you don't need to check whether set contains result before adding, because set won't add a duplicate element. And in the end you could just output s.size(). Counter c is pointless

→ Reply