Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

CQTSC 2010 内部白点

题意:
给你N<=100000个点  同样x坐标的形成竖线段 同样y坐标的形成横线段
让你求出竖线段和横线段的交点数,包括端点。

做法:
我的做法是先求出非端点的交点 最后答案便是 tot+N

先将数组复制一遍 一个数组按照1关键字x 2关键字y排序 另一个关键字顺序反一反
将x或者y离散化 这里以y为例
因为已经按y排过序 所以所有横线段已经都能得到了(相邻一段相同y坐标的点属于同一条线段)
并标记每条横线段的两个端点。

然后我们枚举按x坐标由左边向右边的每条竖线段
我们只要求出有多少横线段与它有交 便是这条竖线段形成的交点数
这等价于求出在当前x坐标的情况下 横线段的右端点x坐标大于当前竖线段x坐标的线数
这样就可以用线段树或者树状数组维护y坐标的点(即维护当前还存在的线段)就可以了

如何维护呢?
对于一条竖线段 我们枚举形成当前竖线的所有点 如果某个点已经是横线段的结尾 那就从树中删除这个y坐标
反之如果是横线段的开始 那就加入这个y坐标
在枚举之前当然要求当前线的交点个数:
对于枚举到的相邻两个相同x坐标的点 假设y1<y2  我们求出 [y1,y2)的存在的线段个数 那便是交点个数

这样就在NLogN时间内解决了此题

ps:发觉我的基础太差了。。二分查找[y1,y2)的两个端点时候竟然忘记了 (y2-1)这个坐标事实上可能不存在
所以二分查找找端点的时候挂了。。BS我把

本题加强版是 dhx学长 出的 Religious
 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 #define n 100005
 5 struct Tpoint
 6 {
 7     #define x0(i) p0[i].x
 8     #define y0(i) p0[i].y
 9     #define nod0(i) p0[i].nod
10     #define x1(i) p1[i].x
11     #define y1(i) p1[i].y
12     #define nod1(i) p1[i].nod
13     int x,y,nod;
14 }    p0[n],p1[n];
15 int N,ny[n],New,T[n],ret=0;
16 bool sta[n],end[n];
17 inline bool cmp0(const Tpoint &a,const Tpoint &b)
18 {
19     return a.y<b.y||a.y==b.y&&a.x<b.x;
20 }
21 inline bool cmp1(const Tpoint &a,const Tpoint &b)
22 {
23     return a.x<b.x||a.x==b.x&&a.y<b.y;
24 }
25 inline int find(int x)
26 {
27     int l=0,r=New;
28     for (int mid=(l+r)>>1;l+1<r;mid=(l+r)>>1)
29     if (ny[mid]<=x)    l=mid;
30     else    r=mid;
31     if (x<ny[r])    return l;
32     return r;
33 }
34 inline int Sum(int x)
35 {
36     int ret=0;
37     for (;x;x-=x&-x)
38         ret+=T[x];
39     return ret;
40 }
41 inline void Add(int x,int delt)
42 {
43     for (;x<=N;x+=x&-x)
44         T[x]+=delt;
45 }
46 int main()
47 {
48     scanf("%d",&N);
49     for (int i=0;i<N;++i)
50     {
51         scanf("%d%d",&x0(i),&y0(i));
52         nod0(i)=i;nod1(i)=i;
53         x1(i)=x0(i),y1(i)=y0(i);
54     }
55     sort(p0,p0+N,cmp0);
56     sta[nod0(0)]=end[nod0(N-1)]=1;
57     for (int i=1;i<N;++i)
58         sta[nod0(i)]=(y0(i)!=y0(i-1));
59     for (int i=0;i<N-1;++i)
60         end[nod0(i)]=(y0(i)!=y0(i+1));
61     ny[++New]=y0(0);
62     for (int i=1;i<N;++i)
63     if (y0(i)!=y0(i-1))    ny[++New]=y0(i);
64     sort(p1,p1+N,cmp1);
65     for (int i=0,k;i<N;i=k)
66     {
67         for (k=i+1;k<N&&x1(i)==x1(k);++k)
68         if (y1(k-1)<y1(k)-1)
69             ret+=Sum(find(y1(k)-1))-Sum(find(y1(k-1)));
70         for (int j=i;j<k;++j)
71         {
72             if (sta[nod1(j)]&&!end[nod1(j)])
73                 Add(find(y1(j)),1);
74             if (!sta[nod1(j)]&&end[nod1(j)])
75                 Add(find(y1(j)),-1);
76         }
77     }
78     printf("%d\n",N+ret);
79     return 0;
80 }
81 

posted on 2010-04-17 20:56 jsn1993 阅读(286) 评论(0)  编辑 收藏 引用 所属分类: Data Structures


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理