比赛 Asm_Def战记之透明计算网络 评测结果 AAAATTTTTA
题目名称 Asm_Def的模拟赛 最终得分 50
用户昵称 Fmuckss 运行时间 10.118 s
代码语言 C++ 内存使用 27.46 MiB
提交时间 2015-11-01 11:57:02
显示代码纯文本
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #define maxn 305
  6. #define inf 1005
  7. using namespace std;
  8. bool use[maxn][maxn],use2[maxn][maxn][maxn];
  9. struct node{
  10. int x,y;
  11. bool edg;
  12. bool chos;
  13. }ns[maxn];
  14. int n,amax,ans;
  15. bool cmp(node a,node b){
  16. return a.y==b.y ? a.x<b.x:a.y<b.y;
  17. }
  18. void read(){
  19. scanf("%d",&n);
  20. for(int i=1;i<=n;i++){
  21. scanf("%d %d",&ns[i].x,&ns[i].y);
  22. use[n][n]=true;
  23. }
  24. sort(ns+1,ns+n+1,cmp);
  25. for(int i=1;i<=n;i++){
  26. int tmpx=ns[i].x,tmpy=1;
  27. while(tmpx==ns[i].x){
  28. if(tmpy){
  29. ns[i].edg=true;
  30. tmpy=0;
  31. i++;
  32. continue;
  33. }
  34. ns[i].edg=false;
  35. i++;
  36. }
  37. i--;
  38. ns[i].edg=true;
  39. }
  40. }
  41. int s(int x1,int y1,int x2,int y2,int x3,int y3){
  42. return abs(x1*y2+y1*x3+x2*y3-y2*x3-y1*x2-y3*x1);
  43. }
  44. void solve(){
  45. for(int i=1;i<=n;i++){
  46. if(!ns[i].edg) continue;
  47. int x1=ns[i].x,y1=ns[i].y;
  48. for(int j=1;j<=n;j++){
  49. if(use[i][j]||i==j||(!ns[j].edg))continue;
  50. int x2=ns[j].x,y2=ns[j].y;
  51. use[i][j]=true;use[j][i]=true;
  52. for(int k=1;k<=n;k++){
  53. if(use2[i][j][k])continue;
  54. if(k==i||k==j||(!ns[j].edg))continue;
  55. int x3=ns[k].x,y3=ns[k].y;
  56. int tot=0;
  57. for(int m=1;m<=n;m++){
  58. int x4=ns[m].x,y4=ns[m].y;
  59. int tmp1=s(x1,y1,x2,y2,x3,y3),
  60. tmp2=s(x1,y1,x2,y2,x4,y4),
  61. tmp3=s(x1,y1,x4,y4,x3,y3),
  62. tmp4=s(x4,y4,x2,y2,x3,y3);
  63. if(tmp1==tmp2+tmp3+tmp4){
  64. tot++;
  65. }
  66. }
  67. if(tot==amax){
  68. ans++;
  69. }else if(tot>amax){
  70. amax=tot;
  71. ans=1;
  72. }
  73. }
  74. }
  75. }
  76. }
  77. int main(){
  78. freopen("trib.in","r",stdin);
  79. freopen("trib.out","w",stdout);
  80. read();
  81. solve();
  82. printf("%d\n%d",amax,ans/3);
  83. return 0;
  84. }