比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 C
题目名称 Asm.Def找燃料 最终得分 0
用户昵称 我只是来打个酱油…… 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-11-04 11:59:02
显示代码纯文本
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. struct node
  6. {
  7. int x;
  8. int y;
  9. int num;
  10. } sa[111]={};
  11. bool flag[111]={};
  12. int n,maxn=10010,ans=0;
  13. bool mycmp(node a,node b)
  14. {
  15. return (a.x<b.x||(a.x==b.x&&a.y<b.y));
  16. }
  17. bool mycmp2(node a,node b)
  18. {
  19. return a.num>b.num;
  20. }
  21. void print()
  22. {
  23. for (int i=1;i<=n;i++)
  24. cout<<sa[i].x<<' '<<sa[i].y<<' '<<"sa[i].num:"<<sa[i].num<<endl;
  25. }
  26. void init()
  27. {
  28. cin>>n;
  29. int a,b,m=0;
  30. for (int i=1;i<=n;i++)
  31. {
  32. scanf("%d%d",&a,&b);
  33. sa[i].x=a; sa[i].y=b; sa[i].num=1;
  34. }
  35. sort(sa+1,sa+n+1,mycmp);
  36. for (int i=2;i<=n;i++)
  37. if (sa[i].x==sa[i-1].x&&sa[i].y==sa[i-1].y)
  38. {
  39. sa[i].num+=sa[i-1].num;
  40. sa[i-1].x=-maxn; sa[i-1].y=-maxn; sa[i-1].num=-1;
  41. m++;
  42. }
  43. sort(sa+1,sa+n+1,mycmp2);
  44. n-=m;
  45. // print();
  46. }
  47. void work()
  48. {
  49. for (int i=1;i<n;i++) // 起始点 A
  50. {
  51. for (int j=i+1;j<=n;j++) // 两点定一直线;
  52. {
  53. if (sa[i].x==sa[j].x)
  54. {
  55. int tmp=sa[i].num+sa[j].num;
  56. for (int k=j+1;k<=n;k++)
  57. if (flag[k]==false&&sa[k].x==sa[i].x)
  58. {
  59. tmp+=sa[k].num;
  60. flag[k]=true;
  61. }
  62. if (tmp>ans) ans=tmp;
  63. }
  64. else {
  65. int tmp=sa[i].num+sa[j].num;
  66. double ka=sa[i].x-sa[j].x;
  67. ka/=(sa[i].y-sa[j].y);
  68. double ba=1.0*sa[i].y-sa[i].x*ka;
  69. flag[j]=true;
  70. for (int k=j+1;k<=n;k++) // 是否经过
  71. if (flag[k]==false)
  72. {
  73. double tmpy=ka*sa[k].x+ba;
  74. if (tmpy==sa[k].y)
  75. {
  76. flag[k]=true;
  77. tmp+=sa[k].num;
  78. }
  79. }
  80. if (tmp>ans) ans=tmp;
  81. }
  82. }
  83. memset(flag,0,sizeof(flag));
  84. }
  85. }
  86. int main()
  87. {
  88. freopen("asm_fuel.in","r",stdin);
  89. freopen("asm_fuel.out","w",stdout);
  90. init();
  91. work();
  92. cout<<ans<<endl;
  93. return 0;
  94. }