比赛 |
Asm_Def战记之透明计算网络 |
评测结果 |
AAAAWWAAWA |
题目名称 |
Asm_Def的模拟赛 |
最终得分 |
70 |
用户昵称 |
Satoshi |
运行时间 |
0.176 s |
代码语言 |
C++ |
内存使用 |
0.32 MiB |
提交时间 |
2015-11-01 09:32:25 |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <stack>
#define N 310
using namespace std;
ifstream in("trib.in");
ofstream out("trib.out");
int n;
vector<int> H;
stack<int> S;
bool vis[N]={0};
class point
{
public:
int x;
int y;
double co;
point operator +(const point a)
{
point b;
b.x=x+a.x;
b.y=y+a.y;
return b;
}
point operator -(const point a)
{
point b;
b.x=x-a.x;
b.y=y-a.y;
return b;
}
int operator *(const point a)
{
int solo;
solo=x*a.x+y*a.y;
return solo;
}
int operator ^(const point a)
{
int solo;
solo=x*a.y-y*a.x;
return solo;
}
void print()
{
out<<x<<' '<<y<<endl;
}
}po[N],start,end;
bool com(point a,point b)
{
if(a.y<b.y)return 1;
if(a.y==b.y)
{
if(a.x<b.x)return 1;
}
return 0;
}
bool som(point a,point b)
{
if(a.co>b.co)return 1;
if(a.co==b.co)
{
if(a*a<b*b)return 1;
}
return 0;
}
void getHull()
{
int i,af,bf;
int s=0;
point a,b;
S.push(1);S.push(2);S.push(3);
for(i=4;i<=n;i++)
{
while(true)
{
af=S.top();S.pop();
bf=S.top();S.push(af);
a=po[af]-po[bf];
b=po[bf]-po[i];
s=a^b;
if(s>0)S.pop();
else break;
}
S.push(i);
}
while(!S.empty())
{
H.push_back(S.top());
S.pop();
}
}
bool check(int a,int b,int c,int d)//判断d是否在三角形A,B,C内
{
int SA=0,SB=0,SC=0,SD;
bool flag=0;
point A,B,C,D,E,F;
A=po[a]-po[d];B=po[b]-po[d];C=po[c]-po[d];
SA=A^B;SB=B^C;SC=C^A;
if(SA<=0&&SB<=0&&SC<=0)flag=1;
if(SA>=0&&SB>=0&&SC>=0)flag=1;
return flag;
}
void work()
{
int i,j,k,l;
int ans1=0,ans2=0,temp=0;
int I,J,K,L;
for(i=0;i<H.size();i++)
{
I=H[i];
for(j=i+1;j<H.size();j++)
{
J=H[j];
for(k=j+1;k<H.size();k++)
{
K=H[k];
temp=0;
//out<<H[i]<<' '<<H[j]<<' '<<H[k]<<endl;
for(l=1;l<=n;l++)
{
if(l==I||l==J||l==K)continue;//重点
if(vis[l])continue;//凸包上的点
if(check(I,J,K,l))temp++;
}
if(temp>ans1)ans1=temp;
//out<<temp<<endl;
}
}
}
for(i=0;i<H.size();i++)
{
I=H[i];
for(j=i+1;j<H.size();j++)
{
J=H[j];
for(k=j+1;k<H.size();k++)
{
K=H[k];
temp=0;
//out<<H[i]<<' '<<H[j]<<' '<<H[k]<<endl;
for(l=1;l<=n;l++)
{
if(l==I||l==J||l==K)continue;//重点
if(vis[l])continue;//凸包上的点
if(check(I,J,K,l))temp++;
}
if(temp==ans1)ans2++;
}
}
}
ans1+=3;
out<<ans1<<' '<<ans2<<endl;
}
void work2()
{
int i,j,k,l;
int ans1=0,ans2=0,temp=0;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
for(k=j+1;k<=n;k++)
{
temp=0;
for(l=1;l<=n;l++)
{
if(l==i||l==j||l==k)continue;
if(check(i,j,k,l))temp++;
}
if(temp>ans1)ans1=temp;
}
}
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
for(k=j+1;k<=n;k++)
{
temp=0;
for(l=1;l<=n;l++)
{
if(l==i||l==j||l==k)continue;
if(check(i,j,k,l))temp++;
}
if(temp==ans1)ans2++;
}
}
}
ans1+=3;
out<<ans1<<' '<<ans2<<endl;
}
int main()
{
int i,u;
in>>n;
for(i=1;i<=n;i++)in>>po[i].x>>po[i].y;
sort(po+1,po+n+1,com);
start=po[1];
for(i=n;i>=1;i--)po[i]=po[i]-po[1];
//for(i=1;i<=n;i++)po[i].print();
for(i=1;i<=n;i++)
{
po[i].co=atan2(double(po[i].x),double(po[i].y));
if(po[i].x==0&&po[i].y==0)po[i].co=9999;
}
sort(po+1,po+n+1,som);
getHull();
for(i=0;i<H.size();i++)vis[H[i]]=1;
//out<<H.size()<<endl;
/*for(i=0;i<H.size();i++)
{
u=H[i];
out<<u<<' ';
end = po[u] + start;
end.print();
}*/
if(n>=100)work();
else
{
work2();
}
return 0;
}