vijos1697——平面几何

vijos1697
标算是并查集。。。

但是我看了下题解，好特么长

然后我想了想，感觉可以BF过掉啊

开始怀疑会不会不连通……

但是看到题目后面的提示

不会询问不在输入里的直线….(..再说这个也啥用啊…)..

于是果断BF

把每一条边当成一个节点，p[i]=-1表示第i个点不确定状态，0表示
处于第一种状态，1表示第二种状态（横竖无所谓）

然后因为不用担心不连通，所以我们可以假设p[1]=1

然后去跑一遍BF，平行的话边权为0，垂直的话边权为1
那么很显然，如果p[x]！=-1 p[y]=p[x]^边权

然后就可以判断一下是不是矛盾的情况

void BF() {For(i,1,cnt){if(vis[i]) continue;if(p[fro[i]]==-1) continue;vis[i]=1;int t=p[fro[i]]^v[i];if(p[poi[i]]!=-1&&p[poi[i]]!=t) end=1;if(end) break;if(p[poi[i]]==-1)flag=1;p[poi[i]]=t;} }

然后是平行线的对数，我们可以记录第一种状态的数量为t1,那么第一种状态中的对数就是C(2,t1) 也就是t1*(t1-1)/2同理第二种状态t2
所以总数就是t1*(t1-1)/2+t2*(t2-1)/2

（以及输入部分写法是问章峥大佬的%%%

CODE:

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<map> #include<cstring> #include<cstdlib> #include<vector> #define inf 1e9 #define end fuck #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; int n,m,q; int poi[10001],nxt[10001],v[10001],f[10001],cnt,fro[10001],p[10001],vis[20001]; bool end,flag; inline void add(int x,int y,int z) {poi[++cnt]=y;fro[cnt]=x;nxt[cnt]=f[x];v[cnt]=z; } void BF() {For(i,1,cnt){if(vis[i]) continue;if(p[fro[i]]==-1) continue;vis[i]=1;int t=p[fro[i]]^v[i];if(p[poi[i]]!=-1&&p[poi[i]]!=t) end=1;if(end) break;if(p[poi[i]]==-1)flag=1;p[poi[i]]=t;} } int main() {cin>>n>>m>>q;char s1[11];For(i,1,n) p[i]=-1;p[1]=1;For(i,1,m){int x,y,z;scanf("%s",s1);x=atoi(s1+1);scanf("%s",s1);if (s1[0]=='v') z=1;else z=0;scanf("%s",s1);y=atoi(s1+1);add(x,y,z); add(y,x,z);}while(1){flag=0;BF();if(end) {printf("There must be something wrong...\n");return 0;}if(!flag) break;}int t1=0,t2=0;For(i,1,n)if(p[i]==1) t1++;else if(p[i]==0) t2++;printf("%d\n",t1*(t1-1)/2+t2*(t2-1)/2);For(i,1,q){int x,y,z;scanf("%s",s1);x=atoi(s1+1);scanf("%s",s1);y=atoi(s1+1);if(p[x]==p[y])printf("Parallel.\n");else printf("Vertical.\n");} }

总结

以上是生活随笔为你收集整理的vijos1697——平面几何的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。