千分留念

积分：1006
提交：125 / 414

话说这题dp真的不好想= =
然后把b[i][k]打成b[i][j]，这个脑残错误调了两节课= =

我们画图可以发现，如果两个线段相交，则每个线段的两个端点(在圆周上)所对应的劣弧极角区间一定相交,我们计算出这些极角区间，离散化，然后求出有多少对区间相交即可(需要使用线段树/树状数组/平衡树维护),时间复杂度为$\Large O(n\log_2n)$
连立方程,
$\Large ax+by+c=0$
$\Large x^2+y^2=r^2$
得
$\Large x=\frac {-ac\pm \sqrt {(ac)^2+(b^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$
$\Large y=\frac {-bc\pm \sqrt {(bc)^2+(a^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$
然而，一些极角区间可能跨过了0度线,我们不妨称之为智障区间，比如[300,30],我们把这些区间记两次数，以[300,390]计算一次，[-60,30]计算一次，可以保证这两次智障区间和非智障区间相交的对只会被计算一次，然而智障区间和智障区间相交的对被计算了两次，再对所有的智障区间计算一次并减掉即可

DFS+剪枝

这个可以完全隐式遍历trie（rank1），也可以半隐式遍历（不存儿子全部存在的节点）

回复 @fmj : 666666

搞基排序真慢= =
O(4*N)事件与O(2*N)空间干不过O(N*lgN)QAQ

速度快的一比

回复 @stdafx.h :
有时间我会加

没有spj啊.. 一个树可能有好几个重心

蒟蒻600T留念。。。。。。

建图迟迟想不到啊

第一竟然打表！！！！！！！！！！！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50 + 10;
class kanato{//Kanato-chan——.//
public:
int sp, re, st;//speaker, reference, status.
bool fa;//false(is not ...).
}sen[maxn];//sentence.
bool night = false;
int sta[maxn], is[maxn], n;
inline int f(bool flag){//false==1貌似会不被判断为真...orz Update: 废话. 懒得重打就这么凑合着看吧.
if(flag)return 1;
return 0;
}
inline bool check(){
bool flag = false;//这句话是否成立.
for(int i=1;i<=n;i++){//逐个检验每句话关于时间与身份的信息.
if(sen[i].re==-1){//关于时间.
if(sen[i].st==f(night))flag = true;
else flag = false;
}
else if(sen[i].st<3){//关于身份.
if(sen[i].st==sta[sen[i].re])flag = true;
else flag = false;
}
else if((sta[sen[i].re]==1)||(sta[sen[i].re]==2)&&night)flag = true;//魔鬼或者是晚上的人.
else flag = false;
//对于说这句话的家伙.
if(sen[i].fa)flag = !flag;//"Is not ...".
if((sta[sen[i].sp])==1||(sta[sen[i].sp]==2&&night))flag = !flag;
if(flag==false)//如果这句话不成立.
return false; //那就无解咯.
}
return true;//找到了一个可行解.
}
inline bool impos(bool a){
for(int i=1;i<=5;i++)if(!is[i])return true;
if(!a)return true;
return false;
}
#define is_cha(x) ((x <= 'z' and x >= 'a') or (x <= 'Z' and x >= 'A'))
#define is_sym(x) ( x == '.' or x == ':' or x == ' ')
#define is_ch(x) (is_sym(x) or is_cha(x))
string get_line() {
char tmp = getchar();
string ans;
ans.clear();
while(!is_ch(tmp)) tmp = getchar();
while( is_ch(tmp)) {
ans = ans + tmp;
tmp = getchar();
}
return ans;
}
int main(){
freopen("logicisland.in", "r", stdin);
freopen("logicisland.out", "w", stdout);
int kase = 0;
//while(cin>>n){getchar();if(n==0)break;kase++;cout<<"Conversation #"<<kase<<endl;
memset(is, 0, sizeof(is));
memset(sta, 0, sizeof(sta));
memset(sen, 0, sizeof(sen));
night = false;
cin>>n;//getchar();//Read char '/n'.
for(int i=1;i<=n;i++){
string str;
str = get_line();
int name = str[0] - 'A' + 1, ref = -1;//Speaker， Mentioned.
str = str.substr(3, str.length());
if(str[0]=='I'&&str[2]=='a'){//I am.
ref = name;
str = str.substr(5, str.length());//go over.
}
else if(str[2]=='i'&&str[3]=='s'){//X is.
ref = str[0] - 'A' + 1;
str = str.substr(5, str.length());//go over.
}
else {//It is night/day.
ref = -1;//算了用中文注释吧, 没有人被提到的情况ref设为-1.
str = str.substr(6, str.length());//继续往后面找相关信息.
}
sen[i].sp = name;sen[i].re = ref;
if(str[0]=='n'&&str[1]=='o'){sen[i].fa = true;str = str.substr(4, str.length());}//Is not.
else sen[i].fa = false;
//
string tmp = "121213413";tmp = tmp.substr(1, tmp.length());
if(str.compare("divine.")==0)sen[i].st = 0;
else if(str.compare("evil.")==0)sen[i].st = 1;
else if(str.compare("human.")==0)sen[i].st = 2;
else if(str.compare("lying.")==0)sen[i].st = 3;
else if(str.compare("day.")==0)sen[i].st = 0;
else if(str.compare("night.")==0)sen[i].st = 1;
else cout<<"Orz Cstdio"<<endl;//哎嘿.
}
//枚举, 搞大新闻.
int tnight = 0, kount = 0;
for(night=false;kount<=1;night=!night, kount++)
for(sta[1]=0;sta[1]<=2;sta[1]++)
for(sta[2]=0;sta[2]<=2;sta[2]++)
for(sta[3]=0;sta[3]<=2;sta[3]++)
for(sta[4]=0;sta[4]<=2;sta[4]++)
for(sta[5]=0;sta[5]<=2;sta[5]++)
if(check()){
for(int j=1;j<=5;j++)is[j] |= (1<<sta[j]);//拆二进制存储状态. 1, 2, 4.
tnight = tnight | (1<<f(night));
}
if(impos(tnight)){cout<<"This is impossible."<<endl<<endl;return 0;}//continue;}
bool flag = false;//有没有找到的推论.
for(int j=1;j<=5;j++){//先输出身份信息.
string out;//cout<<is[j]<<endl;
if(is[j]==(1<<0))out = "divine.";
else if(is[j]==(1<<1))out = "evil.";
else if(is[j]==(1<<2))out = "human.";
else continue;
flag = true;
printf("%c is ", (char)(j+'A'-1));cout<<out<<endl;
}
if(tnight==(1<<0)){flag = true;cout<<"It is day."<<endl;}
if(tnight==(1<<1)){flag = true;cout<<"It is night."<<endl;}
if(flag==false)cout<<"No facts are deducible."<<endl;
cout<<endl;
return 0;
}

注意数组别开小了！！！