首页 >> 大全

cdoj1341卿学姐与城堡的墙

2023-12-09 大全 34 作者：考证青年

Hint

上图是样例的解释，交点是A,B,C

思路：

城堡学校绘画__幼儿园城堡主题墙图片

对所有直线进行预处理（只保存和uv的交点）这是很容易想到的，不过一开始不知道有种东西叫逆序对，只想到n*n的算法。。。。。。。

逆序对的求法有好几种我用的是归并的方法。。

不过这个题要考虑边界情况，如果按u边界的y排序的话，就需要对u边界上的点特殊处理，其实就是u边界上的点扫一遍就好了，，，

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 
17 vectorlong long ,long long > >p;
18 long long  a[200000+5];
19 long long  temp[200000+5];
20 long long  cnt=0;//逆序对的个数
21 double cnm_lg(int n,int m)
22 {
23     int i;
24     double s1=0.0,s2=0.0;
25     for(i=1;i<=m;i++)
26         s1 += log(i);
27     for(i=n-m+1;i<=n;i++)
28         s2 += log(i);
29     return s2-s1;
30 }
31 long long  cnm_double(int n,int m)
32 {
33     if(n<m)
34         return 0;
35     if(m > n/2)
36     m = n-m;
37     return (long long)exp(cnm_lg(n,m));
38 }
39 void merge(int left,int mid,int right)
40 {
41     int i=left,j=mid+1,k=0;
42     while (( i<=mid )&& (j<=right))
43           if (a[i]];
44           else {
45               cnt+=mid+1-i;//关键步骤
46               temp[k++]=a[j++];
47           }
48     while (i<=mid) temp[k++]=a[i++];
49     while (j<=right) temp[k++]=a[j++];
50     for (i=0,k=left; k<=right;) a[k++]=temp[i++];
51 }
52 void mergeSort(int left,int right)
53 {
54     if (left<right)
55     {    int mid=(left+right)/2;
56          mergeSort(left, mid);
57          mergeSort(mid+1, right);
58          merge(left, mid, right);
59     }
60 }
61 int main (void)
62 {
63     int n,u,v;
64     cin>>n>>u>>v;
65     for(int i=0;i)
66     {
67         long long k,b;
68         scanf("%lld%lld",&k,&b);
69         p.push_back(make_pair(b+u*k,b+v*k));
70     }
71     sort(p.begin(),p.end());
72     p.push_back(make_pair(0,1000000000));
73     pair<long ,long >temp=p[0];
74     temp.second=0;
75     for(int i=1;i<=n;i++)
76         if(temp.first != p[i].first || i==n)
77         {
78             cnt+=cnm_double(i-temp.second,2);
79             temp.first=p[i].first;temp.second=i;
80         }
81     if(u==v)
82     {
83         cout<return 0;
84     }
85     for(int i=0;i)
86         a[i]=p[i].second;
87     mergeSort(0,n-1);
88     cout<endl;
89     return 0;
90 }

View Code

tags: 边界 排序 直线 城堡 特殊
其他相关
考证青年

鱼子酱：女人吃的“黑珍珠”

01-10 30
考证青年

Go第七篇之规范的接口

01-07 37
考证青年

两年半Python练习生~收藏一份练习，建议收藏

01-06 28
考证青年

考研数据结构易错选择题

01-06 36
考证青年

与更多热闹的怪胎情人节一起赢取怪胎爱

01-05 35
考证青年

Android项目杰尼杰尼（极简番茄工作法）的学习准备之Android时钟

01-04 34
最新文章

利用区块链等技术，加强对交通运输信用信息的归集共享和分析应用

01-11 319

印尼西爪哇梳邦县发生山体滑坡 已经导致2人死亡

01-11 403

【SpringBoot笔记10】Spring中Bean的6种作用域

01-11 301

ARS548 ARS549RDI 80GHZ毫米波雷达达学习笔记（一)

01-11 330

叠氮PEG修饰二硒化钨 (N3-WSe2；azide

01-11 368

ATFX：黑海运粮遭俄暂停，小麦期货开盘跳涨

01-11 278

关于我们

最火推荐

小编推荐

联系我们

版权声明：本站内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 88@qq.com 举报，一经查实，本站将立刻删除。备案号：桂ICP备2021009421号
Powered By Z-BlogPHP.
复制成功
微信号:
我知道了