根据“点在圆内”关系，列出点P(x0,y0)在圆C(x,y)内的关系：
(x-x0)^2+(y-y0)^2 <= x^2+y^2
化简得：
2*x0*x+2*y0*y >= x0^2+y0^2
然后我们就可以把一个点当成一条线，一个圆当成一个点，通过上面的表达式来转换，这样“点在圆内”的关系就转化成了“点在半平面内”的关系。这样原问题就转化成了不断的加点，然后询问是否所有点都在某个半平面中。
这个东西因为“某一个点在不在半平面中”对”所有点都在半平面中“的答案贡献独立（前者拥有一票否决权），又没有强制在线，所以可以使用对时间分治的思想，以多一个log的复杂度将”边加点边询问问题“变成”先把所有点都加进去，再询问问题“，而后者可以在O(nlogn)时间复杂度内搞定，所以可以在O(nloglog)的时间复杂度内解决。
这道题开始看错题的限制了，题目中限制的是圆心坐标的范围，没有限制询问点坐标的范围，所以就挂了。
/**************************************************************
Problem: 2961
User: idy002
Language: C++
Result: Accepted
Time:6708 ms
Memory:96872 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define N 500010
#define eps 1e-10
using namespace std; int sg( double x ) { return (x>-eps)-(x<eps); }
struct Vector {
double x, y;
void read() {
scanf( "%lf%lf", &x, &y );
}
Vector(){}
Vector( double x, double y ):x(x),y(y){}
Vector operator+( const Vector &b ) const { return Vector(x+b.x,y+b.y); }
Vector operator-( const Vector &b ) const { return Vector(x-b.x,y-b.y); }
Vector operator*( double b ) const { return Vector(x*b,y*b); }
Vector operator/( double b ) const { return Vector(x/b,y/b); }
double operator^( const Vector &b ) const { return x*b.y-y*b.x; }
double operator&( const Vector &b ) const { return x*b.x+y*b.y; }
double ang() { return atan2l(y,x); }
bool operator<( const Vector &b ) const {
return sg(x-b.x)< || (sg(x-b.x)== && sg(y-b.y)<);
}
};
typedef Vector Point;
struct Line {
Point p;
Vector u;
double ang;
int id;
bool ok;
void read( int id ) {
double x, y;
double a, b, c;
scanf( "%lf%lf", &x, &y );
a=x+x, b=y+y;
c=x*x+y*y; if( sg(a)== && sg(b)== ) {
p.x = p.y = 0.0;
u.x = 1.0;
u.y = 0.0;
} else {
if( sg(a)!= )
p.x = c/a, p.y = 0.0;
else
p.x = 0.0, p.y = c/b;
u.x = -b, u.y = a;
if( sg(u^(Point(0.0,0.0)-p))>= )
u.x=-u.x, u.y=-u.y;
} ok = true;
this->id = id;
ang = u.ang();
}
};
struct Job {
int opt;
Point pt;
Line ln;
void read( int id ) {
scanf( "%d", &opt );
if( opt== ) pt.read();
else ln.read(id);
}
}; int n;
Job job[N];
int ans[N];
Point cvx[N];
double lang[N]; bool onleft( Line &l, Point &p ) { // <=
return sg( l.u^(p-l.p) ) >= ;
}
bool onleft( Point &a, Point &b, Point &p ) { // <
return sg( (b-a)^(p-a) ) > ;
}
int convex( vector<Point> &p ) {
sort( p.begin(), p.end() );
int n=p.size();
int m;
cvx[m=] = p[];
for( int i=; i<n; i++ ) {
while( m> && !onleft(cvx[m-],cvx[m],p[i]) ) m--;
cvx[++m] = p[i];
}
int k=m;
for( int i=n-; i>=; i-- ) {
while( m>k && !onleft(cvx[m-],cvx[m],p[i]) ) m--;
cvx[++m] = p[i];
}
return m; // n>=2
}
void binary( int lf, int rg, vector<Point> &vp, vector<Line> &vn ) {
if( lf==rg ) {
if( job[lf].opt== )
vp.push_back( job[lf].pt );
else
vn.push_back( job[lf].ln );
return;
}
vector<Point> lvp;
vector<Line> rvn;
int mid=(lf+rg)>>;
binary( lf, mid, lvp, vn );
binary( mid+, rg, vp, rvn );
//--
Point kpt;
if( lvp.empty() || rvn.empty() ) {
// do nothing
} else if( lvp.size()== ) {
for( int t=; t<rvn.size(); t++ ) {
if( !rvn[t].ok ) continue;
if( !onleft(rvn[t],lvp[]) )
rvn[t].ok = false;
}
} else {
int n = convex( lvp );
for( int t=; t<n; t++ )
lang[t] = (cvx[(t+==n?:t+)]-cvx[t]).ang();
int vid = ;
for( int t=; t<n; t++ )
if( lang[t]>lang[(t+==n?:t+)] ) {
vid = (t+==n?:t+);
break;
}
rotate( cvx, cvx+vid, cvx+n );
rotate( lang, lang+vid, lang+n );
for( int t=; t<rvn.size(); t++ ) {
if( !rvn[t].ok ) continue;
int tt;
if( rvn[t].ang<=lang[] || rvn[t].ang>=lang[n-] ) {
tt = ;
} else {
int lf=, rg=n-;
while( lf<rg ) {
int mid=(lf+rg)>>;
if( lang[mid]>rvn[t].ang ) {
rg = mid;
} else {
lf = mid+;
}
}
tt = lf;
}
int pt = tt==?n-:tt-;
int nt = tt==n-?:tt+;
if( !onleft(rvn[t],cvx[tt])
||!onleft(rvn[t],cvx[pt])
||!onleft(rvn[t],cvx[nt]) ) {
rvn[t].ok=false;
}
}
}
//--
for( int t=; t<lvp.size(); t++ )
vp.push_back( lvp[t] );
for( int t=; t<rvn.size(); t++ )
vn.push_back( rvn[t] );
}
int main() {
scanf( "%d", &n );
bool ok = false;
for( int i=; i<=n; i++ ) {
job[i].read(i);
job[i].ln.ok = ok;
if( job[i].opt== ) ok=true;
}
vector<Line> vn;
vector<Point> vp;
binary( , n, vp, vn );
for( int i=; i<=n; i++ )
ans[i] = -;
for( int t=; t<vn.size(); t++ )
ans[vn[t].id] = vn[t].ok;
for( int i=; i<=n; i++ ) {
if( ans[i]==- ) continue;
printf( "%s\n", ans[i] ? "Yes" : "No" );
}
}