比赛 |
Asm_Def战记之透明计算网络 |
评测结果 |
AWAWWWAAWW |
题目名称 |
Asm_Def的模拟赛 |
最终得分 |
40 |
用户昵称 |
debug |
运行时间 |
0.045 s |
代码语言 |
C++ |
内存使用 |
0.29 MiB |
提交时间 |
2015-11-01 11:51:51 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct ff
{
int x,y;
}f[333]={};
int n;
int maxx=-1;
int shuliang=0;
bool bunengyong[333]={};
double xielv[4]={};
int check2(int a,int b,int c,int d)
{
int zuo=999999;
zuo=min(f[a].x,zuo);
zuo=min(f[b].x,zuo);
zuo=min(f[c].x,zuo);
if(zuo>f[d].x)//在左端的左边
return 0;
int you=-999999;
you=max(f[a].x,you);
you=max(f[b].x,you);
you=max(f[c].x,you);
if(you<f[d].x)//在右端的右边
return 0;
//下面计算斜率,可以看出,两点均在左端或右端不影响结果;
if(xielv[0]>xielv[1])
swap(xielv[0],xielv[1]);
if(xielv[2]>xielv[3])
swap(xielv[3],xielv[2]);
double te=(1.0*f[d].y-f[a].y)/(1.0*f[d].x-f[a].x);
if(!(te<=xielv[1]&&te>=xielv[0]))
return 0;
te=(1.0*f[c].y-f[d].y)/(1.0*f[c].x-f[d].x);
if(!(te<=xielv[3]&&te>=xielv[2]))
return 0;
return 1;//左右条件均符合,即为在三角形内
}
void check(int a,int b,int c)
{
if(f[a].x>f[b].x)
swap(a,b);
if(f[a].x>f[c].x)
swap(a,c);
if(f[b].x>f[c].x)
swap(b,c);
xielv[0]=(1.0*f[b].y-f[a].y)/(1.0*f[b].x-f[a].x);
xielv[1]=xielv[2]=(1.0*f[c].y-f[a].y)/(1.0*f[c].x-f[a].x);
xielv[3]=(1.0*f[c].y-f[b].y)/(1.0*f[c].x-f[b].x);
xielv[0]-=0.00000000001;
xielv[1]+=0.00000000001;
xielv[2]-=0.00000000001;
xielv[3]+=0.00000000001;
int temp=0;
for(int i=1;i<=n;i++)
if(i==a||i==b||i==c)
continue;
else if(check2(a,b,c,i)==1)
temp++,bunengyong[i]=1;
if(temp>maxx)
maxx=temp,shuliang=1;
else if(temp==maxx)
shuliang++;
}
int main()
{
freopen("trib.in","r",stdin);
freopen("trib.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&f[i].x,&f[i].y);
for(int i=1;i<=n-2;i++)
{
if(bunengyong[i])
continue;
for(int j=i+1;j<=n-1;j++)
{
if(bunengyong[j])
continue;
for(int k=j+1;k<=n;k++)
{
if(bunengyong[k])
continue;
check(i,j,k);
}
}
}
printf("%d\n%d\n",maxx+3,shuliang);
}