NC16521. 塔防
描述
输入描述
第一行一个整数n (1 ≤ n ≤ 200)。
接下来n行每行三个整数X_i, Y_i, W_i(0 ≤ |X_i|, |Y_i| ≤ 1,000,000,000, W_i ∈ {0,1})。(X_i, Y_i)表示每个塔的坐标。W_i表示每个塔的属性，如果W_i = 0表示这个塔可以拆除，否则表示这个塔不可拆除。
数据保证没有重点。
输出描述
输出一行表示答案，即有多少种方案。
示例1
输入:
5 0 0 0 0 2 0 2 0 0 2 2 0 1 1 1
输出:
4
示例2
输入:
8 0 0 0 0 1 1 0 2 0 1 2 1 2 2 0 2 1 1 2 0 0 1 0 1
输出:
7
示例3
输入:
6 0 0 0 0 4 0 4 0 0 4 4 0 2 2 1 2 1 0
输出:
11
C++14(g++5.4) 解法, 执行用时: 802ms, 内存消耗: 1132K, 提交时间: 2019-02-15 20:39:10
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-')f=-f;
for(;ch>='0'&&ch<='9';ch=getchar())
x=x*10+ch-'0';
return x*f;
}
inline void chkmin( int &a,int b ) { if(a>b) a=b; }
inline void chkmax( int &a,int b ) { if(a<b) a=b; }
#define _ read()
namespace edge {
const int N=2e5+5;
struct Edge { int to,nxt; }e[N<<1];
int head[N],cnt=0;
inline void clr() { memset(head,-1,sizeof(head)); }
inline void insert( int u,int v ) { e[cnt]=(Edge) { v,head[u] }; head[u]=cnt++; }
inline void ins( int u,int v ) { insert(u,v); insert(v,u); }
}
const int mod=1e9+7;
const ll INF=1e18;
ll xx,yy;
struct point {
ll x,y;
int w;
bool operator <(const point &temp)const {
if(abs((y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy))==0)
return abs(x-xx)+abs(y-yy)>abs(temp.x-xx)+abs(temp.y-yy);
return (y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy)<0;
}
}pt[205];
int cnt_no,n;
ll inx,iny;
int i,j,s,p,q,ch;
int f[205][205],a[205],ans,vv[205][205],num_vv[205],cnt[205][205],ex[205],can[205][205];
int main() {
cin>>n;
for(i=0;i<n;i++)
cin>>pt[i].x>>pt[i].y>>pt[i].w;
for(i=0;i<=n;i++) {
if(!i)
ex[i]=1;
else
ex[i]=(ex[i-1]<<1)%mod;
}
ans=0;
while(n>=3) {
inx=INF;
for(i=0;i<n;i++) {
if(inx>pt[i].x) {
inx=pt[i].x;
iny=pt[i].y;
ch=i;
}
else if(inx==pt[i].x) {
if(iny>pt[i].y) {
iny=pt[i].y;
ch=i;
}
}
}
swap(pt[0],pt[ch]);
xx=pt[0].x;
yy=pt[0].y;
sort(pt+1,pt+n);
for(j=0;j<n;j++)
for(s=0;s<n;s++)
f[j][s]=0;
for(i=0;i<n;i++)
num_vv[i]=0;
cnt_no=0;
for(i=1;i<n;i++) {
if(pt[i].w)
a[cnt_no++]=i;
}
memset(can,0,sizeof(can));
memset(cnt,0,sizeof(cnt));
for(j=0;j<n;j++) {
for(s=0;s<n;s++) {
if(j==s)
continue;
ll mx,my,x1,y1,x2,y2,x3,y3;
x1=pt[j].x-pt[0].x;
y1=pt[j].y-pt[0].y;
x2=pt[s].x-pt[0].x;
y2=pt[s].y-pt[0].y;
if(y2*x1-x2*y1<=0&&j&&s)
continue;
int pp=0;
for(pp=0;pp<cnt_no;pp++) {
p=a[pp];
if(!p||p==j||p==s)
continue;
x3=pt[p].x-pt[0].x;
y3=pt[p].y-pt[0].y;
if(p!=j&&p!=s&&y3*x1-x3*y1>=0&&y3*x2-x3*y2<=0)
break;
}
if(pp>=cnt_no) {
for(p=0;p<n;p++) {
if(!pt[p].w) {
x3=pt[p].x-pt[0].x;
y3=pt[p].y-pt[0].y;
if(p&&p!=j&&p!=s&&y3*x1-x3*y1>=0&&(y3*x2-x3*y2<0||(!(y3*x2-x3*y2)&&!s))) {
x3=pt[s].x-pt[j].x;
y3=pt[s].y-pt[j].y;
ll mx=pt[p].x-pt[j].x,my=pt[p].y-pt[j].y;
if(!j||!s) {
if(y3*mx!=x3*my||pt[p].x>max(pt[j].x,pt[s].x)||pt[p].x<min(pt[j].x,pt[s].x)||pt[p].y>max(pt[j].y,pt[s].y)||pt[p].y<min(pt[j].y,pt[s].y))
continue;
cnt[j][s]++;
}
else if(y3*mx<=x3*my)
cnt[j][s]++;
}
}
}
can[j][s]=1;
vv[j][num_vv[j]++]=s;
if(!j)
f[j][s]=1;
}
}
}
for(j=0;j<n;j++) {
for(s=0;s<n;s++) {
if(!f[j][s])
continue;
ll x1,y1,x2,y2;
x1=pt[s].x-pt[j].x;
y1=pt[s].y-pt[j].y;
f[j][s]=1ll*f[j][s]*ex[cnt[j][s]]%mod;
for(int pp=0;pp<num_vv[s];pp++) {
p=vv[s][pp];
x2=pt[p].x-pt[j].x;
y2=pt[p].y-pt[j].y;
if(y2*x1>x2*y1)
f[s][p]=(f[s][p]+f[j][s])%mod;
}
}
}
for(s=0;s<n;s++) {
if(can[s][0])
ans=(ans+f[s][0])%mod;
}
if(pt[0].w) break;
for(j=1;j<n;j++)
pt[j-1]=pt[j];
--n;
}
cout<<ans<<"\n";
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 707ms, 内存消耗: 1132K, 提交时间: 2018-06-24 04:13:24
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int mod=1e9+7;
const long long inf=1e18;
long long xx,yy;
struct point
{
long long x,y;
int w;
bool operator <(const point &temp)const
{
if(abs((y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy))==0)
return abs(x-xx)+abs(y-yy)>abs(temp.x-xx)+abs(temp.y-yy);
return (y-yy)*(temp.x-xx)-(x-xx)*(temp.y-yy)<0;
}
};
point pt[222];
int cnt_no,n;
int dp[222][222],no_list[222],ans,vec[222][222],num_vec[222],cnt[222][222],ex[222];
bool can[202][202];
int main()
{
scanf("%d",&n);
int i,j,s,p,q,ch;
long long inx,iny;
for(i=0;i<n;i++)
scanf("%lld%lld%d",&pt[i].x,&pt[i].y,&pt[i].w);
for(i=0;i<=n;i++)
{
if(i==0)
ex[i]=1;
else
ex[i]=(ex[i-1]<<1)%mod;
}
ans=0;
while(n>=3)
{
inx=inf;
for(i=0;i<n;i++)
{
if(inx>pt[i].x)
{
inx=pt[i].x;
iny=pt[i].y;
ch=i;
}
else if(inx==pt[i].x)
{
if(iny>pt[i].y)
{
iny=pt[i].y;
ch=i;
}
}
}
swap(pt[0],pt[ch]);
xx=pt[0].x;
yy=pt[0].y;
sort(pt+1,pt+n);
for(j=0;j<n;j++)
for(s=0;s<n;s++)
dp[j][s]=0;
for(i=0;i<n;i++)
num_vec[i]=0;
cnt_no=0;
for(i=1;i<n;i++)
{
if(pt[i].w)
no_list[cnt_no++]=i;
}
memset(can,false,sizeof(can));
memset(cnt,0,sizeof(cnt));
for(j=0;j<n;j++)
{
for(s=0;s<n;s++)
{
if(j==s)
continue;
long long mx,my,x1,y1,x2,y2,x3,y3;
x1=pt[j].x-pt[0].x;
y1=pt[j].y-pt[0].y;
x2=pt[s].x-pt[0].x;
y2=pt[s].y-pt[0].y;
if(y2*x1-x2*y1<=0&&j!=0&&s!=0)
continue;
int pp=0;
for(pp=0;pp<cnt_no;pp++)
{
p=no_list[pp];
if(p==0||p==j||p==s)
continue;
x3=pt[p].x-pt[0].x;
y3=pt[p].y-pt[0].y;
if(p!=j&&p!=s&&y3*x1-x3*y1>=0&&y3*x2-x3*y2<=0)
break;
}
if(pp>=cnt_no)
{
for(p=0;p<n;p++)
{
if(pt[p].w==0)
{
x3=pt[p].x-pt[0].x;
y3=pt[p].y-pt[0].y;
if(p!=0&&p!=j&&p!=s&&y3*x1-x3*y1>=0&&(y3*x2-x3*y2<0||(y3*x2-x3*y2==0&&s==0)))
{
x3=pt[s].x-pt[j].x;
y3=pt[s].y-pt[j].y;
long long mx=pt[p].x-pt[j].x,my=pt[p].y-pt[j].y;
if(j==0||s==0)
{
if(y3*mx!=x3*my||pt[p].x>max(pt[j].x,pt[s].x)||pt[p].x<min(pt[j].x,pt[s].x)||pt[p].y>max(pt[j].y,pt[s].y)||pt[p].y<min(pt[j].y,pt[s].y))
continue;
cnt[j][s]++;
}
else if(y3*mx<=x3*my)
cnt[j][s]++;
}
}
}
can[j][s]=true;
vec[j][num_vec[j]++]=s;
if(j==0)
dp[j][s]=1;
}
}
}
for(j=0;j<n;j++)
{
for(s=0;s<n;s++)
{
if(dp[j][s]==0)
continue;
long long x1,y1,x2,y2;
x1=pt[s].x-pt[j].x;
y1=pt[s].y-pt[j].y;
dp[j][s]=1LL*dp[j][s]*ex[cnt[j][s]]%mod;
for(int pp=0;pp<num_vec[s];pp++)
{
p=vec[s][pp];
x2=pt[p].x-pt[j].x;
y2=pt[p].y-pt[j].y;
if(y2*x1>x2*y1)
dp[s][p]=(dp[s][p]+dp[j][s])%mod;
}
}
}
for(s=0;s<n;s++)
{
if(can[s][0])
ans=(ans+dp[s][0])%mod;
}
if(pt[0].w!=0)
break;
for(j=1;j<n;j++)
pt[j-1]=pt[j];
n--;
}
printf("%d\n",ans);
return 0;
}