2003-Railroad Conflict
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2003&lang=jp
A列車で行こうは名作。
考え方
新線の始点をA、終点をBとする。
新線と既存路線の交点をAに近い順に並び替える。
このとき他社路線なら高さを反転する。
Aの高さはAに一番近い点の高さとし、交点を順に見ていき高さに変化があるなら、ans=ans+1とする。
実装(C++)
typedef pair<double,int> P; int main(){ int T;cin>>T; Line N; for(;cin>>N[0].x>>N[0].y>>N[1].x>>N[1].y;){ vector<P> pts; int n;cin>>n;Line k;int t,t2; for(int i=0;i<n;i++){ cin>>k[0].x>>k[0].y>>k[1].x>>k[1].y>>t>>t2; if(is_intersect_SS(k,N)){ pts.push_back(P((intersects_SS(N,k)-N[0]).size(),t^t2)); } } std::sort(pts.begin(),pts.end()); if(pts.empty()){ cout<<0<<endl;continue; } int ans=0,now=pts[0].second; for(int i=0;i<(int)pts.size();i++){ if(pts[i].second!=now){ ans++;now=pts[i].second; } } cout<<ans<<endl; } return 0; }