本文主要是介绍HDU - 3465 Life is a Line，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题面
http://acm.hdu.edu.cn/showproblem.php?pid=3465
2.题意
给你一堆直线，求在指定区间内，这里有多少对相交线段
3.思路
求出直线在两个端点的值后，使用归并排序求逆序数
PS:值得注意的坑点，
1.这道题即使取消cin与stdio输入输出相关性，使用cin，cout也会超时
2.排序时，当横坐标相等时，要考虑纵坐标的影响
4.代码
/*****************************************************************> File Name: Cpp_Acm.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年07月30日 星期六 15时58分46秒
*****************************************************************/
# include <cstdio>
# include <cstring>
# include <cctype>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;const int debug = 1;
const int size = 10 + 50000 ;
const int INF = INT_MAX>>1;
const double eps = 1e-6;
typedef long long ll;int tot = 0;
int num[size];template<typename T, typename _Compare>
inline ll merge(T *host, T *guest, int len, int wide, _Compare comp){ int l_p,r_p,gst_p; int start,mid,end; ll ret = 0; for (start=0;start<len;start=end){ l_p = gst_p = start; r_p = mid = start + (wide>>1) < len? start + (wide>>1): len; end = start + wide < len? start + wide: len; while (l_p<mid&&r_p<end){ if (comp(host[l_p],host[r_p])){ guest[gst_p++] = host[l_p++]; ret += r_p - mid; }else { guest[gst_p++] = host[r_p++]; } } while (l_p<mid) { guest[gst_p++] = host[l_p++]; ret += r_p - mid; } while (r_p<end){ guest[gst_p++] = host[r_p++]; } } return ret;
} template<typename T, typename _Compare>
ll mergesort(T *host,int len,_Compare comp){ ll ret = 0; T *guest = new T[len]; for (int wide=1;wide<len;){ ret += merge(host,guest,len,wide<<=1,comp); ret += merge(guest,host,len,wide<<=1,comp); } delete guest; return ret;
} struct val{double l,r;
}v[size];bool cmp(const val& c1,const val& c2){if (c1.l != c2.l)return c1.l < c2.l;return c1.r < c2.r;
}bool cmp2(const val& c1,const val& c2){if (c1.r != c2.r)return c1.r < c2.r;return c1.l < c2.l;
}int main()
{std::ios::sync_with_stdio(false);int i,j;int n;double lb,rb;while (~scanf("%d",&n)){scanf("%lf%lf",&lb,&rb);double x1,x2,y1,y2;int t = 0;for (i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);if (fabs(x1-x2)<eps){x1 -= eps;x2 += eps;//# i--;n--; //# if (lb<x1&&x1<rb){//# t++;//# }//# continue;}double k = (y1 - y2)/(x1 - x2);double b = y1 - k*x1;v[i].l = k*lb + b;v[i].r = k*rb + b;}sort(v,v+n,cmp);printf("%lld\n",mergesort(v,n,cmp2)+t*n);}return 0;
}这篇关于HDU - 3465 Life is a Line的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
