傳送門：hdu 5862 Counting Intersections 題意：對於平行於坐標軸的n條線段，求兩兩相交的線段對有多少個，包括十，T型 官方題解：由於數據限制,只有豎向與橫向的線段才會產生交點,所以先對橫向線段按x端點排序,每次加入一個線段,將其對應的y坐標位置+1,當出現一個豎向線段時 ...
傳送門：hdu 5862 Counting Intersections
題意：對於平行於坐標軸的n條線段，求兩兩相交的線段對有多少個，包括十，T型
官方題解：由於數據限制,只有豎向與橫向的線段才會產生交點,所以先對橫向線段按x端點排序,每次加入一個線段,將其對應的y坐標位置+1,當出現一個豎向線段時,查詢它的兩個y端點之間的和即為交點個數.
註意點：對x坐標排序是對所有線段端點排序；因為可能出現 “ 1-1 “ 這樣的情況，所以對於橫著的線段，需要進行首尾x坐標處理；我的方法是對於x坐標，先按大小排序，如果大小相同，按先橫後豎的方式排序，那麼對於 “ 1- ”這樣的情況，是能夠正確計算的，對於“ -1” 這樣的情況，就得對橫著的線段的右端點+1處理
總結：這類題型非常常見，處理方法也很巧妙，有必要熟練運用。2016百度之星複賽的1003 拍照 也是同類型的題
/************************************************************** Problem:hdu 5862 Counting Intersections User: youmi Language: C++ Result: Accepted Time:2199MS Memory:9124K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d\n",a) #define ptlld(a) printf("%I64d\n",a) #define rep(i,from,to) for(int i=from;i<=to;i++) #define irep(i,to,from) for(int i=to;i>=from;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl const double pi=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } ll Pow(ll base, ll n, ll mo) { if (n == 0) return 1; if (n == 1) return base % mo; ll tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp; } //*************************** int n; const int maxn=100000+10; const ll mod=1000000007; typedef struct Point { int x,y; int id; Point(){}; Point(int _x,int _y,int _id) { x=_x,y=_y,id=_id; } }point; typedef struct Line { point s,e; int dir; Line(){}; Line(point _s,point _e,int _dir) { s=_s,e=_e,dir=_dir; } }line; line ln[maxn]; point p[maxn<<1]; int y[maxn<<1]; bool vis[maxn]; bool cmp(point a,point b) { return a.x==b.x?ln[a.id].dir<ln[b.id].dir:a.x<b.x; } ll c[maxn<<1]; int lowbit(int x) { return x&(-x); } void update(int x,int val) { while(x<=2*n) { c[x]+=val; x+=lowbit(x); } } ll query(int x) { ll res=0; while(x) { res+=c[x]; x-=lowbit(x); } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int T_T; scanf("%d",&T_T); for(int kase=1;kase<=T_T;kase++) { sc(n); int x1,y1,x2,y2; rep(i,1,n) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(y1>y2||x1>x2) { swap(y1,y2); swap(x1,x2); } p[i*2-1]=Point(x1,y1,i); p[i*2]=Point(x2,y2,i); y[i*2-1]=y1,y[i*2]=y2; if(y1==y2) ln[i]=Line(Point(x1,y1,i),Point(x2,y2,i),0),p[i*2].x++;//橫線的右端點+1 else if(x1==x2) ln[i]=Line(Point(x1,y1,i),Point(x2,y2,i),1); } sort(p+1,p+1+2*n,cmp); sort(y+1,y+1+2*n); int k=unique(y+1,y+1+2*n)-(y+1); rep(i,1,2*n) p[i].y=lower_bound(y+1,y+1+k,p[i].y)-(y); rep(i,1,n) ln[i].s.y=lower_bound(y+1,y+1+k,ln[i].s.y)-(y),ln[i].e.y=lower_bound(y+1,y+1+k,ln[i].e.y)-(y); ll ans=0; zeros(c); zeros(vis); rep(i,1,2*n) { int dir=ln[p[i].id].dir; if(dir==0) { if(vis[p[i].id]) update(p[i].y,-1); else { vis[p[i].id]=1; update(p[i].y,1); } } else { if(vis[p[i].id]) continue; vis[p[i].id]=1; ll temp=query(ln[p[i].id].e.y); temp-=query(ln[p[i].id].s.y-1); ans+=temp; } } ptlld(ans); } }
