SRM436 Div2 Medium

500

割り算するのが怖いからccw

view plainprint?

1. typedef complex<double> Point;  
2.   
3. double cross(Point a, Point b)  
4. {  
5.   return (a.real() * b.imag() - a.imag() * b.real());  
6. }  
7.   
8. double dot(Point a, Point b)  
9. {  
10.   return (a.real() * b.real() + a.imag() * b.imag());  
11. }  
12.   
13. namespace CCW{  
14.   enum{ RIGHT = 1, LEFT = -1, FRONT = 2, BACK = 2, OTHER = 0 };  
15. };  
16. int ccw(Point a, Point b, Point c)  
17. {  
18.   b -= a;  
19.   c -= a;  
20.   if( cross(b, c) < 0 )return CCW::RIGHT;  
21.   if( cross(b, c) > 0 )return CCW::LEFT;  
22.   if( dot(b, c) < 0 )return CCW::BACK;  
23.   if( norm(b) < norm(c) )return CCW::FRONT;  
24.   return CCW::OTHER;  
25. }  
26.   
27. class BestView {  
28. public:  
29.   int numberOfBuildings(vector <int> hs)  
30.   {  
31.     const int N = hs.size();  
32.     if (N == 1) return 0;  
33.     if (N == 2) return 1;  
34.   
35.     vector<Point> ps;  
36.     for (int i = 0; i < N; ++i) {  
37.       ps.push_back(Point(i, hs[i]));  
38.     }  
39.   
40.     int mx = 0;  
41.     for (int i = 0; i < N; ++i) {  
42.       int cnt = 0;  
43.       if (i) ++cnt;  
44.       for (int j = 0; j < i - 1; ++j) {  
45.         bool flg = true;  
46.         for (int k = j + 1; k < i; ++k) {  
47.           flg = flg && ccw(ps[j], ps[i], ps[k]) == CCW::RIGHT;  
48.         }  
49.         if (flg) ++cnt;  
50.       }  
51.       if (i + 1 < N) ++cnt;  
52.       for (int j = i + 2; j < N; ++j) {  
53.         bool flg = true;  
54.         for (int k = i + 1; k < j; ++k) {  
55.           flg = flg && ccw(ps[i], ps[j], ps[k]) == CCW::RIGHT;  
56.         }  
57.         if (flg) ++cnt;  
58.       }  
59.       mx = max(mx, cnt);  
60.     }  
61.   
62.     return mx;  
63.   }  
64. };  

typedef complex<double> Point;

double cross(Point a, Point b)
{
  return (a.real() * b.imag() - a.imag() * b.real());
}

double dot(Point a, Point b)
{
  return (a.real() * b.real() + a.imag() * b.imag());
}

namespace CCW{
  enum{ RIGHT = 1, LEFT = -1, FRONT = 2, BACK = 2, OTHER = 0 };
};
int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if( cross(b, c) < 0 )return CCW::RIGHT;
  if( cross(b, c) > 0 )return CCW::LEFT;
  if( dot(b, c) < 0 )return CCW::BACK;
  if( norm(b) < norm(c) )return CCW::FRONT;
  return CCW::OTHER;
}

class BestView {
public:
  int numberOfBuildings(vector <int> hs)
  {
    const int N = hs.size();
    if (N == 1) return 0;
    if (N == 2) return 1;

    vector<Point> ps;
    for (int i = 0; i < N; ++i) {
      ps.push_back(Point(i, hs[i]));
    }

    int mx = 0;
    for (int i = 0; i < N; ++i) {
      int cnt = 0;
      if (i) ++cnt;
      for (int j = 0; j < i - 1; ++j) {
        bool flg = true;
        for (int k = j + 1; k < i; ++k) {
          flg = flg && ccw(ps[j], ps[i], ps[k]) == CCW::RIGHT;
        }
        if (flg) ++cnt;
      }
      if (i + 1 < N) ++cnt;
      for (int j = i + 2; j < N; ++j) {
        bool flg = true;
        for (int k = i + 1; k < j; ++k) {
          flg = flg && ccw(ps[i], ps[j], ps[k]) == CCW::RIGHT;
        }
        if (flg) ++cnt;
      }
      mx = max(mx, cnt);
    }

    return mx;
  }
};