Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 692 words)

【GDUT-ACM】大灌水

难以容忍的两个WA
Problem C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            priority_queue<LL,vector<LL>,greater<LL> > que;
            CLEAR(a);
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++) scanf("%lld",&a[i]);
            sort(a,a+n);
            for(int i=1;i<=m;i++)
            {
                que.push(a[n-i]);
            }
            LL ans=a[n-1];
            for(int i=n-m-1;i>=0;i--)
            {
                LL k=que.top();
                que.pop();
                que.push(k+a[i]);
                ans=max(ans,k+a[i]);
            }
            printf("%lld\n",ans);
        }
    return 0;
}

Problem D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e5;
const LL maxl=1e5+10;
const int inf=99999999;
const float eps=1e-3;
 
LL a[maxn];
bool vis[maxl];
int n,m;
vector<LL> vec;
 
void init();
void solve();
void outp();
 
void get_prime()
{
    vec.clear();
    CLEAR(vis);
    int k=0;
    for (int i = 2; i < maxl;i++)
        if(!vis[i])
        {
            k++;
            vec.push_back(i);
            for (int j = 1; i * j <= maxl; j++)
            {
            vis[i * j] = 1;
            }
        }
}
 
int getfac(LL n)
{
    if (n<2) return 0;
    int h=0,res=0;
    while(h<vec.size())
    {
        if (n%vec[h]==0) res++;
        while (n%vec[h]==0) n/=vec[h];
        h++;
    }
    return res;
}
 
LL pow2(LL n)
{
    if (n<=0) return 1;
    else if (n==1) return 2;
    else if (n&1)
    {
        int k=pow2((n-1)>>1);
        return (k*k)<<1;
    }
    else
    {
        int k=pow2(n>>1);
        return k*k;
    }
}
 
int main()
{
    get_prime();
    int T;
    LL n,m;
    scanf("%d",&T);
    while(T--)
        {
            scanf("%lld%lld",&n,&m);
            if (m%n) {printf("0\n");continue;}
            else if (n==1) {printf("1\n");continue;}
            LL t=m/n;
            //printf("%d\n",getfac(t));
            LL ans=pow2(getfac(t)-1);
            printf("%lld\n",ans);
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1113
    User: semprathlon
    Language: C++
    Result: Wrong Answer
****************************************************************/

=====================================
Problem F
罕见的PE，输出末尾不能有多余空格，防不胜防

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=200;
const int inf=99999999;
const float eps=1e-3;
 
int a[maxn];
 
void init();
void solve();
void outp();
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(a);
            scanf("%d%d",&n,&m);
            int mina=inf,h=0;
            for(int i=0;i<m;i++)
            {
                int k;
                scanf("%d",&k);
                if (k<mina)
                {
                    mina=k;
                    a[h++]=k;
                }
            }
            sort(a,a+h);
            int k=0;
            for(int i=1;i<=n;i++)
            {
                if (k<h-1&&a[k+1]<=i) k++;
                if (i<n) printf("%d ",a[k]);
                else printf("%d",a[k]);
            }
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1121
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1488 kb
****************************************************************/

Problem G

1
2
3
4
5
6
7
8
9
int main()
{
    while(~scanf("%d",&n))
        {
            int k=n/3;
            printf("%d\n",(n%3)?2*k+n%3-1:2*k);
        }
    return 0;
}

Problem E
裸的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int maxn=2e5;
const int inf=99999999;
const float eps=1e-3;
 
int f[maxn];
int n,m;
 
int getf(int n)
{
    if (f[n]==n) return n;
    else return f[n]=getf(f[n]);
}
 
bool unite(int u,int v)
{
    int x=getf(u);
    int y=getf(v);
    if (x!=y)
    {
        f[ y ]=x;return 1;
    }
    else return 0;
}
 
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(f);
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) f[i]=i;
            for(int i=1;i<=m;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                unite(u,v);
            }
            int ans=-1;
            for(int i=1;i<=n;i++)
                if (f[i]==i) ans++;
            printf("%d\n",ans);
        }
    return 0;
}
 
/**************************************************************
    Problem: 1118
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:264 ms
    Memory:2264 kb
****************************************************************/

=====================
还有个来不及提交的！［个人原因，15：26才加入比赛
Problem H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int maxn=2e4;
const int inf=99999999;
const float eps=1e-3;
const pair<int,int> p0=make_pair(0,0);

int a[maxn],f1[maxn],f2[maxn];
pair<int,int> g1[maxn],g2[maxn];

void init();
void solve();
void outp();


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        CLEAR(a);
        CLEAR(f1);
        CLEAR(f2);
        CLEAR(g1);
        CLEAR(g2);
        scanf("%d",&a[1]);
        f1[1]=f2[1]=0;
        g1[1]=g2[1]=p0;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (f1[i-1]<f2[i-1])
            {
                g1[i]=make_pair(a[i],g1[i-1].second);
                g2[i]=make_pair(g1[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g1[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g1[i-1].second);
            }
            else
            {
                g1[i]=make_pair(a[i],g2[i-1].second);
                g2[i]=make_pair(g2[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g2[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g2[i-1].second);
            }

        }
        printf("%d\n",min(f1[n],f2[n]));
    }
}

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 486 words)

【GDUT-ACM】水题差点写跪了，囧

Problem B: 神奇的编码

Description

假如没有阿拉伯数字，我们要怎么表示数字呢
小明想了一个方法如下：
1 -> A
2 -> B
3 -> C
….
25 -> Y
26 -> Z
27 -> AA

28 -> AB
….

现在请你写一个程序完成这个转换

Input

输入的第一个数为一个正整数T,表明接下来有T组数据。
每组数据为一个正整数n ( n <= 1000)

Output

对于每个正整数n,输出他对应的字符串

Sample Input

3 1 10 27

Sample Output

A J AA

没什么神奇的，本质还是进制转换

心急如焚之时，代码风格无比混乱；那个26的倍数的特殊处理，是个大痛点，AC一次耗时25min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;
 
 
int n;
 
void init();
void solve();
void outp();
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            string str;
            scanf("%d",&n);
            //n+=(n-1)/26;
            //n++;
            //if (n%26==0) n--;
            while(n)
            {
                char ch=(n%26)?n%26+'A'-1:(n--,'Z');
                str=ch+str;
                n/=26;
            }
            printf("%s",str.c_str());
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
    for(int i=1;i<=n;i++)
    {
 
    }
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1112
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1484 kb
****************************************************************/

=======================分隔符==============================

题E
自我感觉正确，可是未能在结束前提交。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n;

char* solve(double v,double d);

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            double v,d;
            scanf("%lf%lf",&v,&d);
            puts(solve(v,d));
        }
    return 0;
}

char* solve(double v,double d)
{
    return (char*)(((v*v*sqrt(2.0))/10.0-d>eps)?"Fire":"Retreat");
}

题A
耗时16min，循环队列，简直没有TLE/MLE的理由

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int n;
int que[maxsize],h,r;
 
int EnQ(int id)
{
    if ((r+1)%maxsize!=h)
    {
        r=(r+1)%maxsize;
        que[r]=id;
        return 0;
    }
    else return -1;
}
 
int DeQ()
{
    if (h!=r)
    {
        int t=h;
        h=(h+1)%maxsize;
        return que[t];
    }
    else return -1;
}
 
int Query(int k)
{
    if (h==r) return -1;
    int t=(h<=r)?r-h:maxsize-r+h;
    return (t>=k)?que[(h+k)%maxsize]:-1;
}
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(que);h=r=0;
            int cas,k;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                scanf("%d",&cas);
            switch(cas)
            {
                case 1:scanf("%d",&k);EnQ(k);break;
                case 2:DeQ();break;
                case 3:scanf("%d",&k);
                if (Query(k)>=0) printf("%d\n",Query(k));
                else puts("na li you zhe me duo ren");
                break;
            }
            }
        }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 714 words)

POJ1584-A Round Peg in a Ground Hole - ζёСяêτ - 小優YoU - 博客频道 - CSDN NET

POJ1584-A Round Peg in a Ground Hole - ζёСяêτ - 小優YoU - 博客频道 - CSDN.NET.

转载请注明出处：優YoU  http://user.qzone.qq.com/289065406/blog/1309142308

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//Memory Time
//268K    0MS 

#include<iostream>
#include<cmath>
using namespace std;

const double eps=1e-6;
const double pi=3.141592654;

typedef class NODE
{
	public:
		double x,y;
}pos;

int n;
double PegR;  //钉子半径
pos Peg;  //钉子坐标

int precision(double x);  //精度讨论
double det(double x1,double y1,double x2,double y2);  //叉积
double dotdet(double x1,double y1,double x2,double y2);  //点积
double cross(pos A,pos B,pos C,pos D);
double distant(pos A,pos B);  //计算距离
double angle(pos A,pos B,pos P);  //计算向量PA与PB夹角

bool IsConvexBag(pos* Vectex);  //判断输入的点集是否为凸包(本题保证了输入的点集为按某一时针方向有序)
bool IsIn(pos* Vectex); //判断圆心是否在多边形内部
bool IsFit(pos* Vectex);  //判断圆的半径是否<=其圆心到多边形所有边的最小距离

int main(void)
{
	while(cin>>n && n>=3)
	{
		cin>>PegR>>Peg.x>>Peg.y;
		pos* Vectex=new pos[n+2];  //多边形顶点坐标

		for(int i=1;i<=n;i++)
			cin>>Vectex[i].x>>Vectex[i].y;

		Vectex[0].x=Vectex[n].x;  //封闭多边形
		Vectex[0].y=Vectex[n].y;
		Vectex[n+1].x=Vectex[1].x;
		Vectex[n+1].y=Vectex[1].y;

		if(!IsConvexBag(Vectex))
			cout<<"HOLE IS ILL-FORMED"<<endl;
		else
		{
			bool flag1=IsIn(Vectex);
			bool flag2=IsFit(Vectex);

			if(flag1 && flag2)
				cout<<"PEG WILL FIT"<<endl;
			else
				cout<<"PEG WILL NOT FIT"<<endl;
		}

		delete Vectex;
	}
	return 0;
}

/*精度讨论*/
int precision(double x)
{
	if(fabs(x)<=eps)
		return 0;
	return x>0?1:-1;
}

/*计算点积*/
double dotdet(double x1,double y1,double x2,double y2)
{
	return x1*x2+y1*y2;
}

/*计算叉积*/
double det(double x1,double y1,double x2,double y2)
{
	return x1*y2-x2*y1;
}
double cross(pos A,pos B,pos C,pos D)
{
	return det(B.x-A.x , B.y-A.y , D.x-C.x , D.y-C.y);
}

/*计算距离*/
double distant(pos A,pos B)
{
	return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
}

/*计算角度*/
double angle(pos A,pos B,pos P)
{
	return acos(dotdet(A.x-P.x,A.y-P.y,B.x-P.x,B.y-P.y)/(distant(A,P)*distant(B,P)));
}

/*凸包判断*/
bool IsConvexBag(pos* Vectex)
{
	int direction=0;
	//保存点集Vectex的旋转方向direction   1:右手正螺旋，逆时针   -1:左手正螺旋，顺时针
	for(int i=0;i<=n-1;i++)
	{
		int temp=precision(cross(Vectex[i],Vectex[i+1],Vectex[i+1],Vectex[i+2]));

		if(!direction)   //避免最初的点出现共线的情况
			direction=temp;

		if(direction*temp<0)  //只要Vectex是凸包，那么无论Vectex的旋转方向如何，direction*temp都会>=0
			return false;
	}
	return true;
}

/*判断点与多边形的关系*/
bool IsIn(pos* Vectex)
{
	double CircleAngle=0.0;  //环绕角
	for(int i=1;i<=n;i++)  //注意重复边不计算
		if(precision(cross(Peg,Vectex[i],Peg,Vectex[i+1]))>=0)
			CircleAngle+=angle(Vectex[i],Vectex[i+1],Peg);
		else
			CircleAngle-=angle(Vectex[i],Vectex[i+1],Peg);

	if(precision(CircleAngle)==0)  //CircleAngle=0, Peg在多边形外部
		return false;
	else if(precision(CircleAngle-pi)==0 || precision(CircleAngle+pi)==0)   //CircleAngle=180, Peg在多边形边上(不包括顶点)
	{
		if(precision(PegR)==0)
			return true;
	}
	else if(precision(CircleAngle-2*pi)==0 || precision(CircleAngle+2*pi)==0)   //CircleAngle=360, Peg在多边形边内部
		return true;
	else   //CircleAngle=(0,360)之间的任意角， Peg在多边形顶点上
	{
		if(precision(PegR)==0)
			return true;
	}
	return false;
}

/*判断圆与多边形的关系*/
bool IsFit(pos* Vectex)
{
	for(int i=0;i<=n;i++)
	{
		int k=precision(fabs(cross(Peg,Vectex[i],Peg,Vectex[i+1])/distant(Vectex[i],Vectex[i+1]))-PegR);
		if(k<0)
			return false;
	}
	
	return true;
}
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 596 words)

POJ 1556 The Doors（线段交+最短路） - kuangbin - 博客园

POJ 1556 The Doors（线段交+最短路） - kuangbin - 博客园.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/************************************************************
 * Author        : kuangbin
 * Email         : kuangbin2009@126.com 
 * Last modified : 2013-07-14 10:47
 * Filename      : POJ1556TheDoors.cpp
 * Description   : 
 * *********************************************************/

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>

using namespace std;

const double eps = 1e-8;
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0) return -1;
    else return 1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double _x,double _y)
    {
        x = _x;y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x,y - b.y);
    }
    double operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
};
struct Line
{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e)
    {
        s = _s;e = _e;
    }
};
//判断线段相交
bool inter(Line l1,Line l2)
{
    return 
        max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
        max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
        max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
        max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
        sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&
        sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;
}
double dist(Point a,Point b)
{
    return sqrt((b-a)*(b-a));
}
const int MAXN = 100;
Line line[MAXN];
double dis[MAXN][MAXN];
const double INF = 1e20;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    double x,y1,y2,y3,y4;
    while(scanf("%d",&n) == 1)
    {
        if(n == -1) break;
        for(int i = 1;i <= n;i++)
        {
            scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
            line[2*i-1] = Line(Point(x,y1),Point(x,y2));
            line[2*i] = Line(Point(x,y3),Point(x,y4));
        }
        for(int i = 0;i <= 4*n+1;i++)
            for(int j = 0;j <= 4*n+1;j++)
            {
                if(i == j)dis[i][j] = 0;
                else dis[i][j] = INF;
            }
        for(int i = 1;i <= 4*n;i++)
        {
            int lid = (i+3)/4;
            bool flag = true;
            Point tmp;
            if(i&1)tmp = line[(i+1)/2].s;
            else tmp = line[(i+1)/2].e;
            for(int j = 1;j < lid;j++)
                if(inter(line[2*j-1],Line(Point(0,5),tmp)) == false
                        && inter(line[2*j],Line(Point(0,5),tmp)) == false)
                    flag = false;
            if(flag)dis[0][i] =dis[i][0] = dist(Point(0,5),tmp);
            flag = true;
            for(int j = lid+1;j <= n;j++)
                if(inter(line[2*j-1],Line(Point(10,5),tmp)) == false
                        && inter(line[2*j],Line(Point(10,5),tmp)) == false)
                    flag = false;
            if(flag)dis[i][4*n+1] =dis[4*n+1][i] = dist(Point(10,5),tmp);
        }
        for(int i = 1;i <= 4*n;i++)
            for(int j = i+1;j <=4*n;j++)
            {
                int lid1 = (i+3)/4;
                int lid2 = (j+3)/4;
                bool flag = true;
                Point p1,p2;
                if(i&1)p1 = line[(i+1)/2].s;
                else p1 = line[(i+1)/2].e;
                if(j&1)p2 = line[(j+1)/2].s;
                else p2 = line[(j+1)/2].e;
                for(int k = lid1+1;k < lid2;k++)
                    if(inter(line[2*k-1],Line(p1,p2)) == false
                            && inter(line[2*k],Line(p1,p2)) == false)
                        flag = false;
                if(flag) dis[i][j] = dis[j][i] = dist(p1,p2);
            }
        bool flag = true;
        for(int i = 1;i <= n;i++)
            if(inter(line[2*i-1],Line(Point(0,5),Point(10,5))) == false
                    && inter(line[2*i],Line(Point(0,5),Point(10,5))) == false)
                flag = false;
        if(flag)dis[0][4*n+1] = dis[4*n+1][0] = 10;
        for(int k = 0;k <= 4*n+1;k++)
            for(int i = 0;i <= 4*n+1;i++)
                for(int j = 0;j <= 4*n+1;j++)
                    if(dis[i][k] + dis[k][j] < dis[i][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
        printf("%.2lf\n",dis[0][4*n+1]);
    }
    
    return 0;
}
Follow

Categories

Tags

ACM-ICPC14
AC自动机1
AWS2
Adobe1
Angular1
Apache1
Arch Linux2
BFS2
BIT3
Bestcoder23
Bitset3
Bootstrap1
C++2
CCPC1
Catalan1
CentOS3
Clover2
Compiler1
Contest6
Cpp1
DFS3
DNS1
DP13
DSDT3
Data Analytics2
Dinic1
Docker1
Eclipse1
Expect1
Fibonacci1
Frontend1
GLUT1
GPT1
GUI1
Gentoo1
Geometry1
Git1
Github2
Graduate1
HTML1
Hash2
Heap1
Interview1
JNUOJ1
Java12
K8s1
KMP1
Linux3
Live Archive2
MBR1
MS=DOS1
Mac14
Manhattan1
Multi-Uni5
MySQL8
Möbius反演1
NAS2
NetworkFlow1
NoSQL1
OS2
OpenCV1
OpenGL2
Python10
RMQ1
Regional3
Repost1
Ryzen1
SQLserver1
SSL1
System Design1
TOEFL1
Template3
Tree1
Trie2
UEFI4
UX1
Ubuntu14
Unix1
Windows2
Wordpress3
ZFS1
ZOJ1
ajax1
asm1
css1
cuda1
cudnn1
curl1
docker1
es61
font1
ftp1
git1
gitlab1
hardware1
hdu2
hexo1
html1
https1
iOS1
interview1
java1
javascript1
jdk1
jquery1
js7
json1
kext1
macOS2
network1
nginx4
node1
nodejs1
npm1
php8
python1
react2
react native1
regex1
string4
二分图1
二分查找3
博弈1
容斥原理3
并查集1
并行计算1
微积分1
扫描线3
数列1
数独1
数论1
概率2
模拟4
欧拉回路1
百度之星1
知乎1
离散化1
约瑟夫1
线段树3
组合数学1
网络赛2
背包1
背包问题1
转载博文1
递归1

Subscribe for updates

Links

×