#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const double eps = 1E-6;//误差限
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct Line
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
double a;
double b;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct Point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
double x;
double y;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void readReal(double &v)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
scanf("%lf",&v);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool operator < (Line const &l1,Line const &l2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ //斜率为主序(从小到大)
if(l1.a < l2.a)
return true;
if(l1.a > l2.a)
return false;
//截距为次序(从大倒小,也即从高到低)
return l1.b > l2.b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double y_at_x(Line const &line,double x)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{//返回直线line在x处的y值
return line.a*x + line.b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
Point intersection(Line const &l1,Line const &l2 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{//求直线l1和l2的交点
Point p;
p.x = (l1.b - l2.b)/(l2.a - l1.a);
p.y = y_at_x(l1,p.x);
return p;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int count(vector<Line> &L)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{//统计有多少条可见彩虹
if(L.size() < 2) // 处理平凡情形
return L.size();
// 处理非平凡情形
// 首先对直线按斜率递增排序(平行时截距大者优先)
sort(L.begin(),L.end());
stack<Line> lines;// 半平面所交凸域的边所在直线
stack<Point> points;// 半平面所交凸域的顶点
lines.push(L.front());// 添加第一条直线作为约束
for(vector<Line>::iterator iter = L.begin() + 1;iter != L.end();iter++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{// 不断添加直线约束
while(!points.empty())// 去除多余约束 -- 注意误差处理
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{// 先处理出现平行直线的情形
if(fabs(iter->a - lines.top().a) < eps)
break;
// 处理不含平行直线的情形
Point tmp = points.top();
if(y_at_x(*iter,tmp.x) < tmp.y - eps)
break;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
lines.pop();
points.pop();
}
}
// 添加当前非平行直线作为新的约束
if(fabs(iter->a - lines.top().a) > eps)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
points.push(intersection(*iter,lines.top()));
lines.push(*iter);
}
}
// 凸域的边数即是题目要求解的“可见”彩虹条数
return lines.size();
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int text;
cin>>text;
while(text--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int n;
int i;
scanf("%d",&n);
vector<Line> L(n);//直线集合
for(i = 0;i < n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
readReal(L[i].a);
readReal(L[i].b);
}
printf("%d\n",count(L));
}
return 0;
}