程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5862 Counting Intersections,hduintersections

hdu 5862 Counting Intersections,hduintersections

編輯:C++入門知識

hdu 5862 Counting Intersections,hduintersections


傳送門: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);
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved