これはあまり迷わなかったかな。
https://yukicoder.me/problems/no/743
問題
凸M角形があるとする。各点は順に0~(M-1)のラベルを持つとする。
ここで、このM点を端点とするN個の線分を追加するとする。
線分同士の交点はいくつになるか。なお、同一の点を3つ以上の線分が通過する場合、交点は重複してカウントする。
なお、線分同士が端点を共有することはないものとする。
解法
辺の両端の点を(u,v) (u<v)と表現することにする。
u<xである時、(u,v)と(x,y)が交点を持つにはx<u<yであればよい。
言い換えれば、u<x<vであるようなxのうちv<yとなるものを数え上げればよい。
全頂点に対し、辺の両端のu,vをそれぞれ番号順に並べ、走査しながらBITで数えていくことができる。
- 線分の始点uを処理する場合
- BITのu番目の要素をインクリメントする
- 線分の終端vを処理する場合
- BITで[(u+1),∞]の間の要素数を数える
- BITで始点側に対応するu番目の要素をデクリメントする
int N,M; vector<pair<int,int>> V; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<int,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { cin>>x>>y; V.push_back({min(x,y),-1}); V.push_back({max(x,y),min(x,y)}); } ll ret=0; sort(ALL(V)); FORR(v,V) { if(v.second==-1) { bt.add(v.first,1); } else { bt.add(v.second,-1); ret+=bt(1<<19)-bt(v.second); } } cout<<ret<<endl; }
まとめ
意外にコードもすっきり。