/*
光影切割问题:
不少人爱玩CS。仓库的地面会因为阳光从屋顶的漏洞或者窗口照射进来而形成许多光照区域和阴影区域。
假设不同区域的边界都是直线，我们把这些直线都叫做光影线。并假设没有光影线是平行于Y轴的，且不存在三条
光影线相交于一点的情况。
那么，如果我们需要快速计算某个时刻，在X坐标[A,B]区间的地板上被光影划分成多少块。如何设计算法
题目一旦找不到规律：那么应该通过从最简单的情况开始找规律。
类似于中学里面的找规律题目
两条直线-》一个交点-》空间分成4部分
三条直线->两个交点-》6
三条直线->三个交点->7
每增加一条直线，如果增加m个交点，那么这条直线被新增加的m个交点，分成m+1段。
每一段直线会将原来一块区域分成两块，因此会增加m+1个空间。
牛逼:因此N条直线,M个交点，区域数目为N+M+1
该题转化成直线的交点有多少个的问题。
将N条直线逐一投影到坐标区间上，假设当第k条直线投影到坐标区间的时候，它与之前的k-1条直线的交点是
Nk,那么它使得区间[A,B]之间的平面块增加Nk+1(为什么)，全部直线(N条)都投影完毕后，可以得到区间
[A,B]被平面划分的块数，即1+从1到N对（Nk+1）累加求和 = 1 + N + 1到N对Nk求和 = 1 + N + |交点|
其中：1=区间[A,B]的初始平面数。
因此只要求出所有直线两两相交的交点，然后查找哪些交点在[A,B]之间，进而可以求出平面被划分的块数。
将N条直线的所有交点存储于数组Intersect
原问题再次转化为;查找交点数组的问题
需要对数组进行初始化，实质是计算所有交点的过程。需要查询每条直线是否与其他N-1条直线有交点，初始化的
时间复杂度为O(N^2),每次查询的时间复杂度为O(|Intersect|)
如果在初始化后对所有交点按X轴坐标排序，则复杂度为O(N^2 + |Intersect|*log|Intersect|)，其中
|Intersect|*log|Intersect|为排序时间，之后用二分查找，每次查找时间复杂度为O(log|Intersect|)
解法2:
区域内的交点数目等于一个边界上交点顺序相对与另一个边界交点顺序的逆序总数，
问题转化为求一个N个元素的数组的逆序数
此时问题就可以用归并排序来求逆序数了，时间复杂度为O(N*logN),求N个元素的逆序数的分治思想:
先求前N/2个元素的逆序数，再求后N/2个元素的逆序数，最后在排序过程中合并前后两部分之间的逆序数。
*/
/*
关键:
1 void srand(unsigned seed):设置rand()的随机序列种子，产生特定随机数列，一定要在rand()前面调用
srand(time(NULL));
int temp = rand() % MAXSIZE;
2 区域内的交点数目等于一个边界上交点顺序相对与另一个边界交点顺序的逆序总数，
问题转化为求一个N个元素的数组的逆序数
3 while(fin >> strNum)//将读到的每个数字的字符串形式转换成整数形式
{
pArr[iCnt++] = atoi(strNum);
}
4 if(high - low > 1)//注意，必须确保在至少含有一个元素，如果high- low = 1,此时只有一个元素，不需要排序
5 ofstream fout("sortedData.txt");//输出，想把数据写在文件里面用ofstream
6 牛逼:因此N条直线,M个交点，区域数目为N+M+1
该题转化成直线的交点有多少个的问题。
7 将N条直线逐一投影到坐标区间上，假设当第k条直线投影到坐标区间的时候，它与之前的k-1条直线的交点是
Nk,那么它使得区间[A,B]之间的平面块增加Nk+1(为什么)，全部直线(N条)都投影完毕后，可以得到区间
[A,B]被平面划分的块数，即1+从1到N对（Nk+1）累加求和 = 1 + N + 1到N对Nk求和 = 1 + N + |交点|
其中：1=区间[A,B]的初始平面数。
因此只要求出所有直线两两相交的交点，然后查找哪些交点在[A,B]之间，进而可以求出平面被划分的块数。
将N条直线的所有交点存储于数组Intersect
原问题再次转化为;查找交点数组的问题
需要对数组进行初始化，实质是计算所有交点的过程。需要查询每条直线是否与其他N-1条直线有交点，初始化的
时间复杂度为O(N^2),每次查询的时间复杂度为O(|Intersect|)
如果在初始化后对所有交点按X轴坐标排序，则复杂度为O(N^2 + |Intersect|*log|Intersect|)，其中
|Intersect|*log|Intersect|为排序时间，之后用二分查找，每次查找时间复杂度为O(log|Intersect|)
*/
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <time.h>
const int MAXSIZE = 100;
using namespace std;
void generateData()//产生随机测试数据
{
srand(time(NULL));
ofstream fin("dataSource.txt");
if(!fin)
{
printf("Can't open file!\n");
return;
}
for(int i = 0 ; i < MAXSIZE ; i++)
{
int temp = rand() % MAXSIZE;
fin << temp << ' ';
}
fin.close();
}
int readData(int* pArr)
{
ifstream fin("dataSource.txt");
if(!fin)
{
printf("Can't open file!\n");
return -1;
}
int iCnt = 0;//读取每一个数字之后然后存入
char strNum[100];
while(fin >> strNum)//将读到的每个数字的字符串形式转换成整数形式
{
pArr[iCnt++] = atoi(strNum);
}
fin.close();
return iCnt;
}
int _iCnt = 0;
void mergeSort(int* pArr,int low,int high,int* pTempArr)
{
if(!pArr || !pTempArr || low > high || low < 0 || high < 0)//鲁棒性
{
return;
}
if(high - low > 1)//注意，必须确保在至少含有一个元素，如果high- low = 1,此时只有一个元素，不需要排序
{
int mid = low + (high - low)/2;//先划分
mergeSort(pArr,low,mid,pTempArr);//然后递归求解
mergeSort(pArr,mid,high,pTempArr);
int l = low,m = mid,i = l;
while(l < mid || m < high)
{
//如果右边已经遍历结束，或者两边都没结束但是左边<=右边的话，就归并左边的，此时不存在逆序对
if(m >= high || (l < mid && pArr[l] <= pArr[m]))
{
pTempArr[i++] = pArr[l++];
}
else
{
pTempArr[i++] = pArr[m++];
_iCnt += mid - l;//存在的逆序数为：左边剩余没有被归并到数组中的元素的个数，因为只有比右边大的才留下来了
}
}
for(int i = low ; i < high; i++)//全部归并结束之后，把临时数组里面的元素赋给原来的数组
{
pArr[i] = pTempArr[i];
}
}
}
void writeResult(int* pArr,int iLen)
{
if(!pArr || iLen < 0)
{
return;
}
ofstream fout("sortedData.txt");//输出，想把数据写在文件里面用ofstream
if(!fout)
{
return;
}
for(int i = 0 ; i < iLen ; i++)
{
if((i+1) % 20 == 0)
{
fout << endl;
}
fout << pArr[i] << ' ';
}
}
void process()
{
generateData();
int iArr[MAXSIZE + 1];
int iLen = readData(iArr);
int iTempArr[MAXSIZE+1];
_iCnt = 0;
mergeSort(iArr,0,iLen,iTempArr);
printf("%d\n",_iCnt);
writeResult(iArr,iLen);//将排序后的数据写入文件
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
}