fkxr
Lv.1
https://www.luogu.com.cn/problem/U574407
获赞:93收藏:8浏览:407作品收藏:4
签名:lougu UID 995934 fkxr https://www.luogu.com.cn/problem/U574407
Lv.1
https://www.luogu.com.cn/problem/U574407
签名:lougu UID 995934 fkxr https://www.luogu.com.cn/problem/U574407
在 谁会JS？帮忙看一下哪错了？ 中回复
没法看，点击</>；选择javascript再发；
另外帮我找个人看看这个那错了（dev-c++）
#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
inline li read(){
li x = 0,y = 0,c = gc;
while(!isdigit(c)) y = c,c = gc;
while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
return y == '-' ? -x : x;
}
#define ldb long double
int cnt,tong[510];
struct node{
li x,y;
node(li _x = 0,li _y = 0){x = _x;y = _y;}
}p[510];
inline bool operator < (node q,node w){
return q.x == w.x ? q.y < w.y : q.x < w.x;
}
inline bool cmp(int q,int w){
return p[q].x == p[w].x ? p[q].y < p[w].y : p[q].x < p[w].x;
}
inline node operator + (node q,node w){
return node(q.x + w.x,q.y + w.y);
}
inline node operator - (node q,node w){
return node(q.x - w.x,q.y - w.y);
}
inline li operator * (node q,node w){
return q.x * w.y - q.y * w.x;
}
inline ldb dis(node q,node w){
return sqrtl((q.x - w.x) * (q.x - w.x) + (q.y - w.y) * (q.y - w.y));
}
ldb ans;
struct tb{
vector<int> a;
ldb as;
inline int& operator [] (int x){return a[x];}
}a[260],b[260];
int n,nw[1010],tot;
ldb f[510][510],h[510][510],ds[510][510];
int g[510][510];
int jj[510][510];
bool ff[510][510];
node nwd;
inline bool cpm(int q,int w){
if(p[q].x > nwd.x && p[w].x < nwd.x) return 1;
if(p[q].x < nwd.x && p[w].x > nwd.x) return 0;
if(p[q].x == nwd.x && p[q].y < nwd.y) return 0;
if(p[w].x == nwd.x && p[w].y < nwd.y) return 1;
return (p[q] - nwd) * (p[w] - nwd) > 0;
}
inline bool jiao(node a,node b,node c,node d){
node p1 = a - c,p2 = d - c,p3 = b - c;
if(1.0l * (p1 * p2) * (p3 * p2) >= 0) return 0;
p2 = b - a;p3 = d - a;
return 1.0l * (p1 * p2) * (p3 * p2) > 0;
}
bool shan[260];
int pm[510];
int sx[260];
inline bool cp(int q,int w){
return q > w;
}
bool intb[510];
int st1[1010],ft1,st2[1010],ft2;
inline ldb wk(){
int i;
ft1 = ft2 = 0;
sort(nw + 1,nw + tot + 1);
for(i = 1;i <= tot;++i){
while(ft1 > 1 && ((p[st1[ft1]] - p[st1[ft1 - 1]]) * (p[st1[ft1]] - p[nw[i]]) >= 0)) --ft1;
st1[++ft1] = nw[i];
}
for(i = tot;i;--i){
while(ft2 > 1 && ((p[st2[ft2]] - p[st2[ft2 - 1]]) * (p[st2[ft2]] - p[nw[i]]) >= 0)) --ft2;
st2[++ft2] = nw[i];
}
ldb as = 0;
for(i = 1;i < ft1;++i) as += dis(p[st1[i]],p[st1[i + 1]]);
for(i = 1;i < ft2;++i) as += dis(p[st2[i]],p[st2[i + 1]]);
return as;
}
int main(){
int i,j,k,l,u,v;
n = read();
for(i = 1;i <= n;++i){
a[i].a.resize(2);
p[++cnt].x = read();p[cnt].y = read();tong[cnt] = cnt;
p[++cnt].x = read();p[cnt].y = read();tong[cnt] = cnt;
a[i].as = 2 * dis(p[cnt - 1],p[cnt]);
ans += a[i].as;
}
if(n == 1){printf("%.10lf\n",(double)ans);return 0;}
sort(tong + 1,tong + cnt + 1,cmp);
for(i = 1;i <= cnt;++i) a[tong[i] + 1 >> 1][tong[i] + 1 & 1] = i;
for(i = 1;i <= n;++i) if(a[i][0] > a[i][1]) swap(a[i][0],a[i][1]);
memset(tong,0,sizeof(tong));
sort(p + 1,p + cnt + 1);
for(i = 1;i <= cnt;++i){
int tt = 0;
for(j = 1;j <= cnt;++j) if(i != j) jj[i][++tt] = j;
nwd = p[i];
sort(jj[i] + 1,jj[i] + tt + 1,cpm);
}
for(i = 1;i <= cnt;++i) for(j = i;j <= cnt;++j) ds[i][j] = ds[j][i] = dis(p[i],p[j]);
bool lss = 0,fg = 1;
while(fg){
fg = 0;
for(i = 1;i < n;++i) for(j = i + 1;j <= n;++j){
tot = 0;
for(k = 0;k < a[i].a.size();++k) nw[++tot] = a[i][k];
for(k = 0;k < a[j].a.size();++k) nw[++tot] = a[j][k];
ldb nxt = wk();
if(nxt <= a[i].as + a[j].as){
ans += nxt - a[i].as - a[j].as;
a[i].a.clear();a[i].a.resize(ft1 + ft2 - 2);
for(k = 1;k < ft1;++k) a[i][k - 1] = st1[k];
for(k = 1;k < ft2;++k) a[i][k + ft1 - 2] = st2[k];
a[i].as = nxt;swap(a[j],a[n]);--n;fg = 1;
goto qwq;
}
}
qwq:;
}
for(i = 1;i <= n;++i) for(j = 0;j < a[i].a.size();++j) for(k = 1;k <= n;++k) for(l = 0;l < a[k].a.size();++l) if(i != k || j != l) ff[a[i][j]][a[k][l]] = 1;
while(1){
memset(g,0,sizeof(g));
memset(intb,0,sizeof(intb));
for(i = 1;i <= n;++i) for(j = 0;j < a[i].a.size();++j) intb[a[i][j]] = 1;
for(i = 1;i <= cnt;++i) for(j = 1;j <= cnt;++j) if(!intb[i] || !intb[j]) ff[i][j] = 0;
for(i = 1;i <= cnt;++i) for(j = 1;j <= cnt;++j) f[i][j] = ans;
for(i = 1;i <= n;++i) for(j = 0;j < a[i].a.size();++j) for(k = 1;k <= n;++k) for(l = 0;l < a[k].a.size();++l) if(i != k || j != l){
int p1 = a[i][j],p2 = a[k][l];
if(!ff[p1][p2]) continue;
if((p[p2] - p[p1]) * ((j != a[i].a.size() - 1 ? p[a[i][j + 1]] : p[a[i][0]]) - p[p1]) < 0){
ff[p1][p2] = 0;continue;
}
if((p[p1] - p[p2]) * ((l ? p[a[k][l - 1]] : p[a[k][a[k].a.size() - 1]]) - p[p2]) > 0){
ff[p1][p2] = 0;continue;
}
for(u = 1;u <= n;++u) if(u == n || !lss){
if((i < k || (i == k && j < l)) || !ff[p2][p1]){
for(v = 0;v < a[u].a.size();+喵){
if(jiao(p[p1],p[p2],p[a[u][v]],v ? p[a[u][v - 1]] : p[a[u][a[u].a.size() - 1]])){
ff[p1][p2] = ff[p2][p1] = 0;break;
}
}
}
if(!ff[p1][p2]) break;
if(p1 == a[u][0]){
if((p[p2] - p[p1]) * node(1,-1234567890 - p[p1].y) < 0) h[p1][p2] -= a[u].as;
}
else{
nwd = node(p[a[u][0]].x + 1,-1234567890);
li q1 = (p[p1] - p[a[u][0]]) * node(1,-1234567890 - p[a[u][0]].y),q2 = (p[p2] - p[a[u][0]]) * node(1,-1234567890 - p[a[u][0]].y);
if(q1 > 0 && q2 < 0){
if(1.0l * ((nwd - p[p1]) * (p[p2] - p[p1])) * ((p[a[u][0]] - p[p1]) * (p[p2] - p[p1])) < 0) h[p1][p2] -= a[u].as;
}
else if(q1 < 0 && q2 > 0){
if(1.0l * ((nwd - p[p1]) * (p[p2] - p[p1])) * ((p[a[u][0]] - p[p1]) * (p[p2] - p[p1])) < 0) h[p1][p2] += a[u].as;
}
}
}
}
ldb nwa = ans;int wz = 0;
for(i = 1;i <= n;++i) sx[i] = a[i][0];
sort(sx + 1,sx + n + 1,cp);
for(i = 1;i <= n;++i){
int p1 = sx[i],p2;
if(lss && p[a[n][0]] < p[p1]) continue;
pm[p1] = cnt;
for(j = 1;j < cnt;++j) pm[jj[p1][j]] = j;
for(j = 1;j < cnt && p[jj[p1][j]].x >= p[p1].x;++j){
p2 = jj[p1][j];
if(p[p2].x == p[p1].x && p[p2].y < p[p1].y) break;
if(!ff[p1][p2]) continue;
if(f[p1][p2] > ds[p1][p2] + h[p1][p2]){
f[p1][p2] = ds[p1][p2] + h[p1][p2];
g[p1][p2] = p1;
}
}
for(j = 1;j < cnt && p[jj[p1][j]].x >= p[p1].x;++j){
p2 = jj[p1][j];
if(p[p2].x == p[p1].x && p[p2].y < p[p1].y) break;
for(k = 1;k <= cnt;++k) if(ff[p2][k] && pm[k] > pm[p2]){
if(f[p1][k] > f[p1][p2] + ds[p2][k] + h[p2][k]){
f[p1][k] = f[p1][p2] + ds[p2][k] + h[p2][k];
g[p1][k] = p2;
}
}
}
if(f[p1][p1] < -1e-8){
nwa = f[p1][p1];wz = p1;break;
}
}
if(nwa >= -1e-8) break;
ans += nwa;
nw[tot = 1] = wz;
for(i = g[wz][wz];i != wz;i = g[wz][i]) nw[++tot] = i;
nw[++tot] = wz;
int nxtn = 0;
for(i = 1;i <= n;++i){
nwd = node(p[a[i][0]].x + 1,-1234567890);
bool inn = 0;
for(j = 1;j < tot;++j){
if(p[a[i][0]].x == p[nw[j]].x && p[a[i][0]].y == p[nw[j]].y){
inn = 1;break;
}
if(jiao(p[nw[j]],p[nw[j + 1]],p[a[i][0]],nwd)) inn ^= 1;
}
if(inn){
nwa += a[i].as;u = i;
for(int p1 = 1;p1 <= cnt;++p1) for(int p2 = 1;p2 <= cnt;++p2) if(ff[p1][p2]){
if(p1 == a[u][0]){
if((p[p2] - p[p1]) * node(1,-1234567890 - p[p1].y) < 0) h[p1][p2] += a[u].as;
}
else{
nwd = node(p[a[u][0]].x + 1,-1234567890);
li q1 = (p[p1] - p[a[u][0]]) * node(1,-1234567890 - p[a[u][0]].y),q2 = (p[p2] - p[a[u][0]]) * node(1,-1234567890 - p[a[u][0]].y);
if(q1 > 0 && q2 < 0){
if(1.0l * ((nwd - p[p1]) * (p[p2] - p[p1])) * ((p[a[u][0]] - p[p1]) * (p[p2] - p[p1])) < 0) h[p1][p2] += a[u].as;
}
else if(q1 < 0 && q2 > 0){
if(1.0l * ((nwd - p[p1]) * (p[p2] - p[p1])) * ((p[a[u][0]] - p[p1]) * (p[p2] - p[p1])) < 0) h[p1][p2] -= a[u].as;
}
}
}
}
else b[++nxtn] = a[i];
}
for(i = 1;i <= nxtn;++i) a[i] = b[i];
n = nxtn + 1;
a[n].as = nwa;a[n].a.clear();a[n].a.resize(tot - 1);
for(i = tot;i > 1;--i) a[n][tot - i] = nw[i];lss = 1;
}
printf("%.10lf\n",(double)ans);
return 0;
}
2023-06-02T21:28:06 点赞:0
在 两道编程题（编写程序） 中回复
#include<iostream>
using namespace std;
int main(){
int a;//c++
cin<<a;
for(int b=0;;){
if(喵+b*b==a){
break;
}
b++;
}
cout<<b;
return 0;
}2023-07-13T17:23:28 点赞:0
在 两道编程题（编写程序） 中回复
#include<iostream>
using namespace std;
int main(){
int a;//c++
cin>>a;
int b=0;
for(;;){
if(2*b+b*b==a){
int c=b;
break;
}
b++;
}
cout<<b;
return 0;
}2023-07-13T17:32:04 点赞:0
在 两道编程题（编写程序） 中回复
#include<iostream>
using namespace std;
int main(){
int a;
int b=0;
for(;;){
if(2*b+b*b+1==a){
break;
}
b++;
}
return 0;
}2023-07-14T07:40:17 点赞:0
在 #include<iostream> using namespace std; int main() 中回复
!a的值
#include<iostream>
#include<cstring>
using namespace std;
int n,a[90],b[90],c[90],f[90],d=0,len_a,len_b=1,len_c=1,len_ans,m=1;
string s;
int main(){
cin>>n;
b[0]=1;
for(int i=1;i<=n;i++){
len_a=0;
int p=i;
while(p>0){
a[len_a++]=p%10;
p/=10;
}
for(int j=0;j<len_a;j++)
for(int k=0;k<=len_b;k++)
c[j+k]+=a[j]*b[k];
for(int j=0;j<len_c;j++)
if(c[j]>9) c[j+1]+=c[j]/10,c[j]%=10;
if(c[len_c]) len_c++;
len_ans=len_b,len_b=len_c,m=max(m,len_c);
for(int k=len_c-1;k>=0;k--) b[k]=c[k];
len_c=len_a+len_ans;
memset(c,0,sizeof(c));
for(int j=0;j<m;j++){
f[j]+=b[j];
if(f[j]>9) f[j+1]+=f[j]/10,f[j]%=10;
}
}
while(!f[m]&&m>0) m--;
for(int i=m;i>=0;i--) cout<<f[i];
return 0;
}
2023-07-30T16:15:06 点赞:0
在 【求助】怎么增加金币（就是从素材商城购买角色、音效等用的金币） 中回复
征用头像shtian的个人中心-洛谷|计算机科学教育新生态(luogu.com.cn)
2024-04-06T21:09:07 点赞:0