极角,扫描。
黑白点等价转换。
关键就是扫描这一小段。
int L = 0, R = 0;
int cnt = 2; // 分割线上的两个点
while( L<k ) {if( L==R ) { R = (R+1)%k; ++cnt; }while( L!=R&&Left( p[L],p[R] ) ) { R = (R+1)%k; ++cnt; }--cnt;++L;ans = max( ans,cnt );
}
这里怎么扫描的?(盗用某评论区的图和文字)
为了简单,所有点都画到一个圆周上去了,现在已经将他们按照极角排序好了。
最开始L = R = 0,经过一轮循环后,R = 6,cnt = 7;
下一轮循环:L = 1,有5次R++和cnt++,但区间左端点变大,所以46行有个cnt–,最后cnt = 10
cnt统计的是区间[L, R]中点的个数,可以把这个区间想象成一个不超过180°的扇形。
当L++后,cnt不需要清零,只需要在原有的基础上,看看R自增了多少次,cnt就自增多少次。因为L++了,区间左端点变大,所以后面还有个cnt–
L==R时,为什么要++cnt?
if( L==R ) { R = (R+1)%k; ++cnt; }
LR时,直线上一共就2个点,为什么还要++呢?这是为了和后面cnt–统一。
后面的cnt–是为了当扫描起点(L)++后,去除旧的起点。而刚开始的时候LR的时候并没有旧的起点,所以我们可以假装它有一个旧的起点(不存在),后面cnt–会删掉的,这样就与后面一致了。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 1000 + 5;struct Point{int x,y;double rad;bool operator < ( const Point &rhs ) const {return rad<rhs.rad;}
};
Point p[N],op[N];int n,color[N];// 点b,在原点(0,0)到点 a 的这条直线的左边吗? 是返回true
bool Left( Point a, Point b ) {return a.x*b.y - a.y*b.x>=0;
}int solve() {int ans = 0;// 轮流做基点 for( int i=0; i<n; ++i ) {int k = 0; //统计除基点外的点for( int j=0; j<n; ++j ) {if( i!=j ) {//相对基点的坐标 p[k].x = op[j].x - op[i].x;p[k].y = op[j].y - op[i].y;//把黑点关于基点对称过去,这样只用算一个180度区间内的点就可以,而不用360度 ,缩小扫描区间 if( color[j] ) {p[k].x = -p[k].x; p[k].y = -p[k].y;}p[k].rad = atan2( p[k].y,p[k].x ); // 算极角++k; }}sort( p,p+k );int L = 0, R = 0;int cnt = 2; // 分割线上的两个点while( L<k ) {if( L==R ) { R = (R+1)%k; ++cnt; }while( L!=R&&Left( p[L],p[R] ) ) { R = (R+1)%k; ++cnt; }--cnt;++L;ans = max( ans,cnt );} }return ans;
}
int main()
{//freopen("in.txt","r",stdin);while(scanf("%d", &n) == 1 && n) {for(int i = 0; i < n; i++)scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);printf("%d\n", solve());}//fclose(stdin);return 0;}