QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464938 | #8209. Curly Palindromes | yzhang | WA | 1ms | 3660kb | C++14 | 1.7kb | 2024-07-06 16:16:43 | 2024-07-06 16:16:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 105
using namespace std;
string val[N];
struct vec{
int x,y;
}p[N];
vec operator - (const vec &a,const vec &b){
return (vec){b.x-a.x,b.y-a.y};
}
ll cross(vec a,vec b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
vector<int> v[26];
int cnt[26],ans=1;
void dfs(vec p1,vec p2,vec p3,vec p4,int len){
ans=max(ans,len);
for(int i=0;i<26;++i)
if(v[i].size()>=2){
if(cross(p1-p[v[i][0]],p2-p1)>0&&cross(p4-p3,p[v[i][1]]-p4)>0)
dfs(p[v[i][0]],p1,p4,p[v[i][1]],len+2);
if(cross(p1-p[v[i][1]],p2-p1)>0&&cross(p4-p3,p[v[i][0]]-p4)>0)
dfs(p[v[i][1]],p1,p4,p[v[i][0]],len+2);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>p[i].x>>p[i].y>>val[i];
++cnt[val[i][0]-'a'];
v[val[i][0]-'a'].push_back(i);
}
for(int i=0;i<26;++i) if(cnt[i]>2) {
cout<<"Infinity";
return 0;
}
for(int i=0;i<26;++i){
for(int j=0;j<v[i].size();++j){
for(int k=0;k<26;++k)
if(v[k].size()==2){
if(cross(p[v[i][j]]-p[v[k][0]],p[v[k][1]]-p[v[i][j]])>0)
dfs(p[v[k][0]],p[v[i][j]],p[v[i][j]],p[v[k][1]],3);
if(cross(p[v[i][j]]-p[v[k][1]],p[v[k][0]]-p[v[i][j]])>0)
dfs(p[v[k][1]],p[v[i][j]],p[v[i][j]],p[v[k][0]],3);
}
}
if(v[i].size()==2){
dfs(p[v[i][0]],p[v[i][1]],p[v[i][0]],p[v[i][1]],2);
dfs(p[v[i][1]],p[v[i][0]],p[v[i][1]],p[v[i][0]],2);
}
}
cout<<ans<<'\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3660kb
input:
4 0 0 o 1 1 c 2 2 p 3 3 c
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 2 3 e 3 2 e 8 9 e
output:
Infinity
result:
ok single line: 'Infinity'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 0 0 p 1 1 c 2 2 o
output:
1
result:
ok single line: '1'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
3 1000000000 1000000000 a 0 1000000000 b 1000000000 0 a
output:
5
result:
wrong answer 1st lines differ - expected: 'Infinity', found: '5'