比赛 |
Asm_Def战记之透明计算网络 |
评测结果 |
AAAATTTTTA |
题目名称 |
Asm_Def的模拟赛 |
最终得分 |
50 |
用户昵称 |
Fmuckss |
运行时间 |
10.118 s |
代码语言 |
C++ |
内存使用 |
27.46 MiB |
提交时间 |
2015-11-01 11:57:02 |
显示代码纯文本
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 305
#define inf 1005
using namespace std;
bool use[maxn][maxn],use2[maxn][maxn][maxn];
struct node{
int x,y;
bool edg;
bool chos;
}ns[maxn];
int n,amax,ans;
bool cmp(node a,node b){
return a.y==b.y ? a.x<b.x:a.y<b.y;
}
void read(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&ns[i].x,&ns[i].y);
use[n][n]=true;
}
sort(ns+1,ns+n+1,cmp);
for(int i=1;i<=n;i++){
int tmpx=ns[i].x,tmpy=1;
while(tmpx==ns[i].x){
if(tmpy){
ns[i].edg=true;
tmpy=0;
i++;
continue;
}
ns[i].edg=false;
i++;
}
i--;
ns[i].edg=true;
}
}
int s(int x1,int y1,int x2,int y2,int x3,int y3){
return abs(x1*y2+y1*x3+x2*y3-y2*x3-y1*x2-y3*x1);
}
void solve(){
for(int i=1;i<=n;i++){
if(!ns[i].edg) continue;
int x1=ns[i].x,y1=ns[i].y;
for(int j=1;j<=n;j++){
if(use[i][j]||i==j||(!ns[j].edg))continue;
int x2=ns[j].x,y2=ns[j].y;
use[i][j]=true;use[j][i]=true;
for(int k=1;k<=n;k++){
if(use2[i][j][k])continue;
if(k==i||k==j||(!ns[j].edg))continue;
int x3=ns[k].x,y3=ns[k].y;
int tot=0;
for(int m=1;m<=n;m++){
int x4=ns[m].x,y4=ns[m].y;
int tmp1=s(x1,y1,x2,y2,x3,y3),
tmp2=s(x1,y1,x2,y2,x4,y4),
tmp3=s(x1,y1,x4,y4,x3,y3),
tmp4=s(x4,y4,x2,y2,x3,y3);
if(tmp1==tmp2+tmp3+tmp4){
tot++;
}
}
if(tot==amax){
ans++;
}else if(tot>amax){
amax=tot;
ans=1;
}
}
}
}
}
int main(){
freopen("trib.in","r",stdin);
freopen("trib.out","w",stdout);
read();
solve();
printf("%d\n%d",amax,ans/3);
return 0;
}