思路:似曾相识?...见http://www.cnblogs.com/qzqzgfy/p/5266874.html
一看时限还是4s!，于是就开开心心地打了70%的分，就是用容斥原理，就可以n^3解决问题了。
实际情况:10分，wtf
我的程序:
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
const double eps=1e-;
int tot[][],n,m,K;
const double Pi=acos(-);
struct Point{
double x,y,ang;
int id,bel;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
}d[],f[],t[],p[];
struct Line{
Point s,e;
Line(){}
Line(Point s0,Point e0):s(s0),e(e0){}
};
int sgn(double x){
if (x<-eps) return -;
if (x>eps) return ;
return ;
}
bool cmp(Point p1,Point p2){
return p1.ang<p2.ang;
}
double operator *(Point p1,Point p2){
return p1.x*p2.y-p1.y*p2.x;
}
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool inter(Line p1,Line p2){
if (std::min(p1.s.x,p1.e.x)>std::max(p2.s.x,p2.e.x)||
std::min(p1.s.y,p1.e.y)>std::max(p2.s.y,p2.e.y)||
std::min(p2.s.x,p2.e.x)>std::max(p1.s.x,p1.e.x)||
std::min(p2.s.y,p2.e.y)>std::max(p1.s.y,p1.e.y))
return ;
double a,b,c,d;
a=(p1.e-p1.s)*(p2.e-p1.s);
b=(p1.e-p1.s)*(p2.s-p1.s);
c=(p2.e-p2.s)*(p1.e-p2.s);
d=(p2.e-p2.s)*(p1.s-p2.s);
return (a*b<=eps)&&(c*d<=eps);
}
void sbpianfen1(){
int ans=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int k=;k<=K;k++)
for (int l=k+;l<=K;l++)
if (inter(Line(d[i],f[j]),Line(t[k],t[l]))) ans++;
printf("%d\n",ans);
}
void updata(Point p1,Point p2,int v){
if (p1.bel+p2.bel!=) return;
if (p1.bel>p2.bel) std::swap(p1,p2);
tot[p1.id][p2.id]+=v;
}
void sbpianfen2(){
for (int i=;i<=K;i++){
int cnt=;
for (int j=;j<=n;j++){
p[++cnt]=d[j];p[cnt].bel=;
p[cnt].ang=atan2(d[j].y-t[i].y,d[j].x-t[i].x);
}
for (int j=;j<=m;j++){
p[++cnt]=f[j];p[cnt].bel=;
p[cnt].ang=atan2(f[j].y-t[i].y,f[j].x-t[i].x);
}
for (int j=;j<=K;j++){
if (j==i) continue;
p[++cnt]=t[j];p[cnt].bel=;
p[cnt].ang=atan2(t[j].y-t[i].y,t[j].x-t[i].x);
}
std::sort(p+,p++cnt,cmp);
for (int j=;j<=cnt;j++){
p[cnt+cnt+j]=p[cnt+j]=p[j];
p[cnt+j].ang=p[j].ang+*Pi;
p[cnt+cnt+j].ang=p[cnt+j].ang+*Pi;
}
int l=;int numl=(p[].bel==);
int numj=,numr=,numk=;
for (int j=;j<=cnt;j++){
if (p[j].bel==) numj++;
int r=j+;numr=numj+(p[j+].bel==);
while (sgn(p[l].ang-p[j].ang-Pi)<) l++,numl+=(p[l].bel==);
for (int k=j+,numk=numj+(p[j+].bel==);sgn(p[k].ang-p[j].ang-Pi)<=;k++,numk+=(p[k].bel==)){
while (sgn(p[r+].ang-p[k].ang-Pi)<=) r++,numr+=(p[r].bel==);
updata(p[k],p[j],numk-numj-(numr-numl+(p[l].bel==)));
}
}
}
int ans=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
ans+=tot[i][j];
printf("%d\n",ans/);
}
int main(){
n=read();
for (int i=;i<=n;i++)
d[i].x=read(),d[i].y=read(),d[i].id=i;
m=read();
for (int i=;i<=m;i++)
f[i].x=read(),f[i].y=read(),f[i].id=i;
K=read();
for (int i=;i<=K;i++)
t[i].x=read(),t[i].y=read(),t[i].id=i;
if (n<=&&m<=&&K<=) {sbpianfen1();return ;}
if (n<=&&m<=&&K<=) {sbpianfen2();return ;}
}
明明应该很科学啊。。
正解:n^2做法，枚举导弹发射井，然后极角排序，统计即可。
具体做法:枚举发射井作为原点，然后将其他类型的点排序，然后一边for走过去，ans就加等于在半平面内的基地数乘以导弹防御塔数，再减去在每个基地后边的导弹防御塔数之和，注意删掉相同极角的部分，这样就是答案了，果然我数学太差了，毛都不会。。。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
const double Pi=acos(-);
ll ans=;
int d[][],n,K,m;
struct Point{
int x,y;
Point(){}
Point(int x0,int y0):x(x0),y(y0){}
}S[],T[],E[];
struct node{
long double w;
Point p;
int bz;
}Q[];
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll operator *(Point p1,Point p2){
return (ll)p1.x*p2.y-(ll)p1.y*p2.x;
}
Point operator -(Point a,Point b){
return Point(a.x-b.x,a.y-b.y);
}
bool cmp(const node a,const node b){
return a.w<b.w||(!(a.p*b.p)&&a.bz<b.bz);
}
long double get(Point a){
long double w=atan2(a.y,a.x);
if (w<) w=w+Pi+Pi;
return w;
}
void calc(Point S){
for (int i=;i<=n;i++) Q[i].w=get(Q[i].p=E[i]-S),Q[i].bz=;
for (int i=;i<=K;i++) Q[i+n].w=get(Q[i+n].p=T[i]-S),Q[i+n].bz=;
for (int i=;i<=n+K;i++){
Q[i+n+K]=Q[i];Q[i+n+K].w=Q[i].w+*Pi;
if (Q[i].bz) Q[i+n+K].bz=;
}
std::sort(Q+,Q++n+K+n+K,cmp);
int sum=,l=,r=,same=;
ll all=,ans1=ans;
for (int i=;i<=n+K+n+K;i++){
while (l<=r&&Q[d[l][]].w+Pi<Q[i].w) all-=d[l++][];
if (Q[i].bz){
if (i!=&&Q[i].p*Q[i-].p) same=;
ans+=(ll)(r-l+)*sum-all;
if (Q[i].bz==) all+=sum-same,d[++r][]=i,d[r][]=sum-same;
}else{
sum++;
if (i!=&&!(Q[i].p*Q[i-].p)) same++;
else same=;
}
}
}
int main(){
n=read();
for (int i=;i<=n;i++) E[i].x=read(),E[i].y=read();
m=read();
for (int i=;i<=m;i++) S[i].x=read(),S[i].y=read();
K=read();
for (int i=;i<=K;i++) T[i].x=read(),T[i].y=read();
for (int i=;i<=m;i++)
calc(S[i]);
printf("%lld\n",ans);
}