记录编号	84069	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov13]视线	最终得分	100
用户昵称	mouse	是否通过	通过
代码语言	C++	运行时间	0.238 s
提交时间	2013-12-09 19:21:46	内存使用	0.31 MiB

#include <fstream>
#include<algorithm>
#include <cmath>
#include<vector>
using namespace std;
#define PI 3.1415926535897932384626
ifstream fin("sight.in");
ofstream fout("sight.out");
vector<pair<double,double> >a;
int find(int l,int r,double x)
{
  int m; bool f=false;
  while(!f)
  {
	if(a[l].first>x) {return l;}
	if(a[r].first<x) {return r+1;}
    m=(l+r)/2;
    if(a[m].first>x) r=m-1;
     else l=m+1;
  }
}
int main()
{
	int n,r;fin>>n>>r;
	for(int i=0;i<n;i++)
	{
	  double x,y;fin>>x>>y;
	  double alpha=acos(r/sqrt(x*x+y*y));
	  double a0=atan2(y,x)-alpha;
	  if(a0<0)a0+=2*PI;
	  a.push_back(make_pair(a0,a0+2*alpha));
	}
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++)
	{
	  a.push_back(make_pair(a[i].first+2*PI,a[i].second+2*PI));
	}
	int ans=0,lo=0;
	for(int i=0;i<n;i++)
	{
	  lo=find(i+1,i+n-1,a[i].second);
	  if(lo<=i)lo=i+1;
	  ans+=lo-i-1;
	}
	fout<<ans<<endl;
	fin.close();fout.close();
	return 0;
}