「NOIP模拟赛」超电磁炮
「题目描述」
早苗入手了最新的超电磁炮。最新款自然有着与以往不同的功能，那就是它的轨迹是条直线，厉害吧。
2维平面上有n个目标，任意2个目标的坐标不会相同。超电磁炮的威力强到穿透一切，那么早苗一枪最多能击中多少目标？
「输入格式」
第1行：一个整数n，表示目标数量。
第2-n+1行：每行有两个整数xi和yi(-2 000 000 000≤xi，yi≤2 000 000 000)，表示第i个教徒在地图中的行、列坐标。
「输出格式」
一个整数表示答案。
「样例输入」
5
0 0
1 1
2 2
0 3
2 3
「样例输出」
3
「数据范围」
对于40%的数据 N<=200;
对于100%的数据 N<=1500；
选定每个点为基点，极角排序然后扫一遍
复杂度n^2logn
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; struct point{ll x,y;}p[2005],t[2005]; inline point sub(point a,point b) {point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;} inline ll cmul(point a,point b) {return a.x*b.y-a.y*b.x;} inline ll turn(point a,point b,point c) {return cmul(sub(b,a),sub(c,a));} inline bool operator<(point a,point b) {return turn(p[0],a,b)<0;} int main() { //freopen("railgun.in","r",stdin); //freopen("railgun.out","w",stdout); n=read(); for(int i=1;i<=n;i++) { t[i].x=read();t[i].y=read(); p[i].x=t[i].x;p[i].y=t[i].y; } for(int i=1;i<=n;i++) { p[0]=t[i]; sort(p+1,p+n+1); int tmp=2; for(int j=2;j<=n;j++) { if(p[j].x==p[0].x&&p[j].y==p[0].y)continue; if(turn(p[0],p[j-1],p[j])==0)tmp++; else ans=max(tmp,ans),tmp=2; } ans=max(tmp,ans); } printf("%d",ans); return 0; } |
Subscribe
计数器 9787339
OI 课件=>
OI 课件=>