61 lines
1.5 KiB
C++
61 lines
1.5 KiB
C++
struct ray
|
|
{
|
|
ll x, y, dx, dy; int i, j;
|
|
ray(pll A, pll B, int i = 0, int j = 0)
|
|
{
|
|
if(A.fi == B.fi && A.se > B.se) swap(A, B), swap(i, j);
|
|
|
|
if(A.fi>B.fi) swap(A, B), swap(i, j);
|
|
this->i = i; this->j = j;
|
|
x = A.fi; y = A.se;
|
|
dx = B.fi-A.fi; dy = B.se-A.se;
|
|
}
|
|
friend bool operator<(const ray& A, const ray& B)
|
|
{
|
|
return (A.dy*B.dx == B.dy*A.dx)?A.x == B.x?A.dx<B.dx:A.x<B.x:(A.dy*B.dx < B.dy*A.dx);
|
|
}
|
|
};
|
|
|
|
const int N = 1005;
|
|
vector<pair<pll, int> > p; vector<ray> vec;
|
|
int num[N];
|
|
|
|
void solve()
|
|
{
|
|
getint(n);
|
|
p.pb({{0, 0}, 0});
|
|
forr(i, n)
|
|
{
|
|
getll(a); getll(b); getchar(c);
|
|
p.pb({{a, b}, c=='R'});
|
|
}
|
|
sort(p.begin()+1, p.end());
|
|
forr(i, n) num[i] = i;
|
|
|
|
Seg s(1, n, p);
|
|
|
|
forr(i, n) fors(j, i+1, n) vec.pb(ray(p[i].fi, p[j].fi, i, j));
|
|
sort(all(vec));
|
|
|
|
ll ans = s.query(1, n).m;
|
|
for(auto r:vec)
|
|
{
|
|
int i = r.i, j = r.j;
|
|
assert(num[i]+1 == num[j]);
|
|
|
|
int ii = p[num[i]].se;
|
|
int jj = p[num[j]].se;
|
|
//printf("%d %d %d %d\n", i, j, ii, jj);
|
|
s.update(num[j], [ii](Dta A){return Dta(ii);});
|
|
//printf("%d\n", s.query(1, n).m);
|
|
s.update(num[i], [jj](Dta A){return Dta(jj);});
|
|
//printf("%d\n", s.query(1, n).m);
|
|
|
|
swap(p[num[i]], p[num[j]]);
|
|
swap(num[i], num[j]);
|
|
|
|
ans = max(ans, (ll)s.query(1, n).m);
|
|
}
|
|
printf("%lld\n", ans);
|
|
}
|