PKU2019数据结构与算法实习作业 22~30

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define T (2 * n + 1)
using namespace std;
int m, n, cnt = 1;
int Q[55], h[55], q[55];
int a[55][55], b[55][55], c[55][55];
struct data{
    int to, next, v;
}e[10005];
int last[55];
void insert(int u, int v, int w)
{
    e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;
    e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;
}
bool bfs()
{
    int head = 0, tail = 1;
    memset(h, -1, sizeof(h));
    q[0] = 0; h[0] = 0;    
    while(head != tail)
    {
        int now = q[head]; head++;
        for(int i = last[now]; i; i = e[i].next)
            if(h[e[i].to] == -1 && e[i].v)
            {
                h[e[i].to] = h[now] + 1;
                q[tail++] = e[i].to;
            }
    }
    return h[T] != -1;
}
int dfs(int x, int f)
{
    if(x == T)return f;
    int w, used = 0;
    for(int i = last[x]; i; i = e[i].next)
        if(h[e[i].to] == h[x] + 1)
        {
            w = dfs(e[i].to, min(f - used, e[i].v));
            used += w;
            e[i].v -= w; e[i ^ 1].v += w;
            if(used == f)return f;
        }
    if(!used)h[x] = -1;
    return used;
}
bool check(int x, int y)
{
    for(int i = 1; i <= m; i++)
        if(a[y][i] == 1 && b[x][i] == 0)
            return 0;
        else if(a[y][i] == 0 && b[x][i] == 1)
            return 0;
    return 1;
}
int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> Q[i];
        bool flag = 0;
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 1)flag = 1;
        }
        if(!flag)insert(0, i, inf);
        flag = 1;
        for(int j = 1; j <= m; j++)
        {
            cin >> b[i][j];
            flag &= b[i][j];
        }
        if(flag)insert(i + n, T, inf);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j && check(i, j))
            {
                c[i][j] = cnt + 1;
                insert(i + n, j, inf);
            }
    for(int i = 1; i <= n; i++)
        insert(i, i + n, Q[i]);
    int ans = 0, ans2 = 0;
    while(bfs())
        ans += dfs(0,inf);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i!=j && e[c[i][j] ^ 1].v)
                ans2++;
    cout << ans << ' ' << ans2 << endl;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i!=j && e[c[i][j] ^ 1].v)
                cout << i << ' ' << j << ' ' << e[c[i][j] ^ 1].v << endl;
    return 0;
}

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

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define T (2 * n + 1)

using namespace std;

int m, n, cnt = 1;

int Q[55], h[55], q[55];

int a[55][55], b[55][55], c[55][55];

struct data{

int to, next, v;

}e[10005];

int last[55];

void insert(int u, int v, int w)

{

e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;

e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;

}

bool bfs()

{

int head = 0, tail = 1;

memset(h, -1, sizeof(h));

q[0] = 0; h[0] = 0;

while(head != tail)

{

int now = q[head]; head++;

for(int i = last[now]; i; i = e[i].next)

if(h[e[i].to] == -1 && e[i].v)

{

h[e[i].to] = h[now] + 1;

q[tail++] = e[i].to;

}

return h[T] != -1;

}

int dfs(int x, int f)

{

if(x == T)return f;

int w, used = 0;

for(int i = last[x]; i; i = e[i].next)

if(h[e[i].to] == h[x] + 1)

{

w = dfs(e[i].to, min(f - used, e[i].v));

used += w;

e[i].v -= w; e[i ^ 1].v += w;

if(used == f)return f;

}

if(!used)h[x] = -1;

return used;

}

bool check(int x, int y)

{

for(int i = 1; i <= m; i++)

if(a[y][i] == 1 && b[x][i] == 0)

return 0;

else if(a[y][i] == 0 && b[x][i] == 1)

return 0;

return 1;

}

int main()

{

cin >> m >> n;

for(int i = 1; i <= n; i++)

{

cin >> Q[i];

bool flag = 0;

for(int j = 1; j <= m; j++)

{

cin >> a[i][j];

if(a[i][j] == 1)flag = 1;

}

if(!flag)insert(0, i, inf);

flag = 1;

for(int j = 1; j <= m; j++)

{

cin >> b[i][j];

flag &= b[i][j];

}

if(flag)insert(i + n, T, inf);

}

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if(i != j && check(i, j))

{

c[i][j] = cnt + 1;

insert(i + n, j, inf);

}

for(int i = 1; i <= n; i++)

insert(i, i + n, Q[i]);

int ans = 0, ans2 = 0;

while(bfs())

ans += dfs(0,inf);

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if(i!=j && e[c[i][j] ^ 1].v)

ans2++;

cout << ans << ' ' << ans2 << endl;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if(i!=j && e[c[i][j] ^ 1].v)

cout << i << ' ' << j << ' ' << e[c[i][j] ^ 1].v << endl;

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, K, C, M, cnt, ans;
int h[305], last[305], q[305];
int a[305][305];
struct data{
    int to, next, v;
}e[1000005];
void insert(int u, int v, int w)
{
    e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;
    e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;
}
bool bfs()
{
    int head = 0, tail = 1;
    memset(h, 0, sizeof(h));
    h[0] = 1; 
    while(head != tail)
    {
        int x = q[head]; head++;
        for(int i = last[x]; i; i = e[i].next)
            if(e[i].v && !h[e[i].to])
            {
                h[e[i].to] = h[x] + 1;
                q[tail++] = e[i].to;
            }
    }
    return h[n + 1];
}
int dfs(int x, int f)
{
    int w, used = 0;
    if(x == n + 1)return f;
    for(int i = last[x]; i; i = e[i].next)
        if(h[e[i].to] == h[x] + 1)
        {
            w = dfs(e[i].to, min(e[i].v, f - used));
            e[i].v -= w; e[i ^ 1].v += w;
            used += w;
            if(used == f)return f;
        }
    if(!used)h[x] = 0;
    return used;
}
bool check(int x)
{
    memset(last, 0, sizeof(last));
    cnt = 1;
    for(int i = 1; i <= K; i++)
        for(int j = K + 1; j <= n; j++)
            if(a[i][j] <= x)
                insert(i, j, inf);
    for(int i = 1; i <= K; i++)
        insert(0, i, M);
    for(int i = 1; i <= C; i++)
        insert(K + i, n + 1, 1);
    ans = 0;
    while(bfs())
        ans += dfs(0, inf);
    return ans == C;
}
int main()
{
    memset(a, 127 / 3, sizeof(a));
    K = read(); C = read(); M = read();
    n = K + C;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int x = read();
            if(x)a[i][j] = x;
        }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    int l = 0, r = 1000000, mid, ans = -1;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(check(mid))ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, K, C, M, cnt, ans;

int h[305], last[305], q[305];

int a[305][305];

struct data{

int to, next, v;

}e[1000005];

void insert(int u, int v, int w)

{

e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;

e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;

}

bool bfs()

{

int head = 0, tail = 1;

memset(h, 0, sizeof(h));

h[0] = 1;

while(head != tail)

{

int x = q[head]; head++;

for(int i = last[x]; i; i = e[i].next)

if(e[i].v && !h[e[i].to])

{

h[e[i].to] = h[x] + 1;

q[tail++] = e[i].to;

}

return h[n + 1];

}

int dfs(int x, int f)

{

int w, used = 0;

if(x == n + 1)return f;

for(int i = last[x]; i; i = e[i].next)

if(h[e[i].to] == h[x] + 1)

{

w = dfs(e[i].to, min(e[i].v, f - used));

e[i].v -= w; e[i ^ 1].v += w;

used += w;

if(used == f)return f;

}

if(!used)h[x] = 0;

return used;

}

bool check(int x)

{

memset(last, 0, sizeof(last));

cnt = 1;

for(int i = 1; i <= K; i++)

for(int j = K + 1; j <= n; j++)

if(a[i][j] <= x)

insert(i, j, inf);

for(int i = 1; i <= K; i++)

insert(0, i, M);

for(int i = 1; i <= C; i++)

insert(K + i, n + 1, 1);

ans = 0;

while(bfs())

ans += dfs(0, inf);

return ans == C;

}

int main()

{

memset(a, 127 / 3, sizeof(a));

K = read(); C = read(); M = read();

n = K + C;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

{

int x = read();

if(x)a[i][j] = x;

}

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

int l = 0, r = 1000000, mid, ans = -1;

while(l <= r)

{

mid = (l + r) >> 1;

if(check(mid))ans = mid, r = mid - 1;

else l = mid + 1;

}

cout << ans << endl;

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
const int maxn=500;
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, T, ans;
int v[405][405], h[405], q[405];
bool bfs()
{
    memset(h, 0, sizeof(h));
    h[0] = 1; q[0] = 0;
    int head = 0, tail = 1;
    while(head != tail)
    {
        int x = q[head]; head++;
        for(int i = 0; i <= T; i++)
            if(!h[i] && v[x][i])
            {
                h[i] = h[x] + 1;
                q[tail++] = i;
            }
    }
    return h[T];
}
int dfs(int x, int f)
{
    if(x == T)return f;
    int used = 0, w;
    for(int i = 0; i <= T; i++)
        if(h[i] == h[x] + 1)
        {
            w = dfs(i, min(f - used, v[x][i]));
            v[x][i] -= w; v[i][x] += w;
            used += w;
            if(used == f)return f;
        }
    if(!used)h[x] = 0;
    return used;
}
int main()
{
    
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(v, 0, sizeof(v));
        T = n + m + 1;
        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int t = read();
            while(t--)
            {
                int x = read();
                v[i][n + x] = 1;
            }
        }
        for(int i = 1; i <= n; i++)
            v[0][i] = 1;
        for(int i = 1; i <= m; i++)
            v[n + i][T] = 1;
        while(bfs())
            ans += dfs(0, inf);
        printf("%d\n", ans);
    }
    return 0;
}

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

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

const int maxn=500;

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, T, ans;

int v[405][405], h[405], q[405];

bool bfs()

{

memset(h, 0, sizeof(h));

h[0] = 1; q[0] = 0;

int head = 0, tail = 1;

while(head != tail)

{

int x = q[head]; head++;

for(int i = 0; i <= T; i++)

if(!h[i] && v[x][i])

{

h[i] = h[x] + 1;

q[tail++] = i;

}

return h[T];

}

int dfs(int x, int f)

{

if(x == T)return f;

int used = 0, w;

for(int i = 0; i <= T; i++)

if(h[i] == h[x] + 1)

{

w = dfs(i, min(f - used, v[x][i]));

v[x][i] -= w; v[i][x] += w;

used += w;

if(used == f)return f;

}

if(!used)h[x] = 0;

return used;

}

int main()

{

while(scanf("%d%d", &n, &m) != EOF)

{

memset(v, 0, sizeof(v));

T = n + m + 1;

ans = 0;

for(int i = 1; i <= n; i++)

{

int t = read();

while(t--)

{

int x = read();

v[i][n + x] = 1;

}

for(int i = 1; i <= n; i++)

v[0][i] = 1;

for(int i = 1; i <= m; i++)

v[n + i][T] = 1;

while(bfs())

ans += dfs(0, inf);

printf("%d\n", ans);

}

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define eps 1e-6
using namespace std;
int n;
struct point{double x,y;};
struct line{point a,b;}s1,s2;
point sub(point a,point b)
{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
double cmul(point a,point b)
{return a.x*b.y-b.x*a.y;}
double turn(point p1,point p2,point p3)
{return cmul(sub(p2,p1),sub(p3,p1));}
bool online(line a,line b)
{
	if(fabs(turn(a.a,a.b,b.a)*turn(a.a,a.b,b.b))>eps)return 0;
	if(fabs(turn(b.a,b.b,a.a)*turn(b.a,b.b,a.b))>eps)return 0;
	return 1;
}
bool par(line a,line b)
{
	if(fabs(cmul(sub(a.a,a.b),sub(b.a,b.b)))<eps)return 1;
	return 0;
}
point cpoint(line a,line b)
{
	double k1,k2,t;
	k1=cmul(sub(a.b,b.a),sub(b.b,b.a));
	k2=cmul(sub(b.b,b.a),sub(a.a,b.a));
	t=k1/(k1+k2);
	point ans;
	ans.x=a.b.x+(a.a.x-a.b.x)*t;
	ans.y=a.b.y+(a.a.y-a.b.y)*t;
	return ans;
}
int main()
{
	printf("INTERSECTING LINES OUTPUT\n");
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf%lf",&s1.a.x,&s1.a.y,&s1.b.x,&s1.b.y);
		scanf("%lf%lf%lf%lf",&s2.a.x,&s2.a.y,&s2.b.x,&s2.b.y);
		if(online(s1,s2))printf("LINE\n");
		else if(par(s1,s2))printf("NONE\n");
		else 
		{
			point ans=cpoint(s1,s2);
			printf("POINT %.2lf %.2lf\n",ans.x,ans.y);
		}
	}
	printf("END OF OUTPUT\n");
	return 0;
}

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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define eps 1e-6

using namespace std;

int n;

struct point{double x,y;};

struct line{point a,b;}s1,s2;

point sub(point a,point b)

{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}

double cmul(point a,point b)

{return a.x*b.y-b.x*a.y;}

double turn(point p1,point p2,point p3)

{return cmul(sub(p2,p1),sub(p3,p1));}

bool online(line a,line b)

{

if(fabs(turn(a.a,a.b,b.a)*turn(a.a,a.b,b.b))>eps)return 0;

if(fabs(turn(b.a,b.b,a.a)*turn(b.a,b.b,a.b))>eps)return 0;

return 1;

}

bool par(line a,line b)

{

if(fabs(cmul(sub(a.a,a.b),sub(b.a,b.b)))<eps)return 1;

return 0;

}

point cpoint(line a,line b)

{

double k1,k2,t;

k1=cmul(sub(a.b,b.a),sub(b.b,b.a));

k2=cmul(sub(b.b,b.a),sub(a.a,b.a));

t=k1/(k1+k2);

point ans;

ans.x=a.b.x+(a.a.x-a.b.x)*t;

ans.y=a.b.y+(a.a.y-a.b.y)*t;

return ans;

}

int main()

{

printf("INTERSECTING LINES OUTPUT\n");

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%lf%lf%lf%lf",&s1.a.x,&s1.a.y,&s1.b.x,&s1.b.y);

scanf("%lf%lf%lf%lf",&s2.a.x,&s2.a.y,&s2.b.x,&s2.b.y);

if(online(s1,s2))printf("LINE\n");

else if(par(s1,s2))printf("NONE\n");

else

{

point ans=cpoint(s1,s2);

printf("POINT %.2lf %.2lf\n",ans.x,ans.y);

}

printf("END OF OUTPUT\n");

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct P{
    int x, y;
}p[105];
int n, ans;
P operator-(P a, P b)
{
    return (P){a.x - b.x, a.y - b.y};
}
int operator*(P a, P b)
{
    return a.x * b.y - a.y * b.x;
}
int cal(int i, int j, int k)
{
    return abs((p[j] - p[i]) * (p[k] - p[i]));
}
bool check(int i, int j, int k)
{
    int tmp = cal(i, j, k);
    for(int x = 1; x <= n; x++)
        if(x != i && x != j && x != k)
        {
            if(cal(x, i, j) + cal(x, j, k) + cal(x, i, k) == tmp)
                return 0;
        }
    return 1;
}
int main()
{
    while(1)
    {
        n = read();
        if(n == 0)break;
        ans = 0;
        char ch[2];
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", ch);
            p[i].x = read(); p[i].y = read();
        }
        int p1=0, p2=0, p3=0;
        for(int i = 1; i <= n; i++)
            for(int j = i + 1; j <= n; j++)
                for(int k = j + 1; k <= n; k++)
                    if(check(i, j, k) && cal(i, j, k) > ans)
                    {                        
                        ans = cal(i, j, k);
                        p1 = i, p2 = j, p3 = k;
                    }
        cout << char(p1 + 'A' - 1) << char(p2 + 'A' - 1) << char(p3 + 'A' - 1) << endl;
    }
    return 0;
}

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct P{

int x, y;

}p[105];

int n, ans;

P operator-(P a, P b)

{

return (P){a.x - b.x, a.y - b.y};

}

int operator*(P a, P b)

{

return a.x * b.y - a.y * b.x;

}

int cal(int i, int j, int k)

{

return abs((p[j] - p[i]) * (p[k] - p[i]));

}

bool check(int i, int j, int k)

{

int tmp = cal(i, j, k);

for(int x = 1; x <= n; x++)

if(x != i && x != j && x != k)

{

if(cal(x, i, j) + cal(x, j, k) + cal(x, i, k) == tmp)

return 0;

}

return 1;

}

int main()

{

while(1)

{

n = read();

if(n == 0)break;

ans = 0;

char ch[2];

for(int i = 1; i <= n; i++)

{

scanf("%s", ch);

p[i].x = read(); p[i].y = read();

}

int p1=0, p2=0, p3=0;

for(int i = 1; i <= n; i++)

for(int j = i + 1; j <= n; j++)

for(int k = j + 1; k <= n; k++)

if(check(i, j, k) && cal(i, j, k) > ans)

{

ans = cal(i, j, k);

p1 = i, p2 = j, p3 = k;

}

cout << char(p1 + 'A' - 1) << char(p2 + 'A' - 1) << char(p3 + 'A' - 1) << endl;

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 1e20
#define eps 1e-5
using namespace std;
int n;double ans;
struct point{double x,y;};
struct line{point a,b;}l[21];
point sub(point a,point b)
{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
double cmul(point a,point b)
{return a.x*b.y-a.y*b.x;}
double turn(point a,point b,point c)
{return cmul(sub(b,a),sub(c,a));}
bool cross(line a,line b)
{
	if(turn(a.a,a.b,b.a)*turn(a.a,a.b,b.b)>0)return 0;
	return 1;
}
point cpoint(line a,line b)
{
    double k1,k2,t;
    k1=cmul(sub(a.b,b.a),sub(b.b,b.a));
    k2=cmul(sub(b.b,b.a),sub(a.a,b.a));
    t=k1/(k1+k2);point cp;
    cp.x=a.b.x+(a.a.x-a.b.x)*t;
    cp.y=a.b.y+(a.a.y-a.b.y)*t;
    return cp;
}
bool equ(point a,point b)
{
	if(fabs(a.x-b.x)>eps)return 0;
	if(fabs(a.y-b.y)>eps)return 0;
	return 1;
}
double cal(line a)
{
	for(int i=1;i<=n;i++)
	    if(!cross(a,l[i]))
	    {
	    	line l1,l2;
	    	if(i==1)return -inf;
	    	l1.a=l[i].a;l1.b=l[i-1].a;
	    	l2.a=l[i].b;l2.b=l[i-1].b;
	    	if(cross(a,l1)&&!equ(cpoint(a,l1),l1.b))return cpoint(a,l1).x;
            else return cpoint(a,l2).x;
	    }
	return inf;
}
void solve()
{
	line t;ans=-inf;
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=n;j++)
	   {
	   	   t.a=l[i].a;t.b=l[j].b;
	   	   ans=max(cal(t),ans);
	   }
    if(ans==inf)printf("Through all the pipe.");
    else printf("%.2lf",ans);
    printf("\n");
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
	    for(int i=1;i<=n;i++)
		{
	        scanf("%lf%lf",&l[i].a.x,&l[i].a.y);
	        l[i].b.x=l[i].a.x;l[i].b.y=l[i].a.y-1;
	    }
	    solve();
	}
	return 0;
}

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define inf 1e20

#define eps 1e-5

using namespace std;

int n;double ans;

struct point{double x,y;};

struct line{point a,b;}l[21];

point sub(point a,point b)

{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}

double cmul(point a,point b)

{return a.x*b.y-a.y*b.x;}

double turn(point a,point b,point c)

{return cmul(sub(b,a),sub(c,a));}

bool cross(line a,line b)

{

if(turn(a.a,a.b,b.a)*turn(a.a,a.b,b.b)>0)return 0;

return 1;

}

point cpoint(line a,line b)

{

double k1,k2,t;

k1=cmul(sub(a.b,b.a),sub(b.b,b.a));

k2=cmul(sub(b.b,b.a),sub(a.a,b.a));

t=k1/(k1+k2);point cp;

cp.x=a.b.x+(a.a.x-a.b.x)*t;

cp.y=a.b.y+(a.a.y-a.b.y)*t;

return cp;

}

bool equ(point a,point b)

{

if(fabs(a.x-b.x)>eps)return 0;

if(fabs(a.y-b.y)>eps)return 0;

return 1;

}

double cal(line a)

{

for(int i=1;i<=n;i++)

if(!cross(a,l[i]))

{

line l1,l2;

if(i==1)return -inf;

l1.a=l[i].a;l1.b=l[i-1].a;

l2.a=l[i].b;l2.b=l[i-1].b;

if(cross(a,l1)&&!equ(cpoint(a,l1),l1.b))return cpoint(a,l1).x;

else return cpoint(a,l2).x;

}

return inf;

}

void solve()

{

line t;ans=-inf;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

t.a=l[i].a;t.b=l[j].b;

ans=max(cal(t),ans);

}

if(ans==inf)printf("Through all the pipe.");

else printf("%.2lf",ans);

printf("\n");

}

int main()

{

while(scanf("%d",&n)&&n)

{

for(int i=1;i<=n;i++)

{

scanf("%lf%lf",&l[i].a.x,&l[i].a.y);

l[i].b.x=l[i].a.x;l[i].b.y=l[i].a.y-1;

}

solve();

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, top;
struct P{
    double x, y;
    friend P operator-(P a, P b){
        return (P){a.x - b.x, a.y - b.y}; 
    }
    friend int operator*(P a, P b){
        return a.x * b.y - a.y * b.x;
    }
    friend bool operator<(P a, P b){
        if(a.y == b.y)return a.x < b.x;
        return a.y < b.y;
    }
    friend int dis2(P a){
        return a.x * a.x + a.y * a.y;
    }
}p[1005], q[1005];
bool cmp(P a, P b)
{
    if((a - p[1]) * (b - p[1]) == 0)
        return dis2(a - p[1]) < dis2(b - p[1]);
    return (a - p[1]) * (b - p[1]) > 0;
}
void graham()
{
    top = 0;
    for(int i = 1; i <= n; i++)
        if(p[i] < p[1])swap(p[i], p[1]);
    sort(p + 2, p + n + 1, cmp);
    for(int i = 1; i <= n; i++)
    {
        while(top > 1 && (q[top] - q[top - 1]) * (p[i] - q[top - 1]) <= 0)
            top--;
        q[++top] = p[i];
    }
}
bool checkline(P a, P b)
{
    for(int i = 1; i <= n; i++)
    {
        if(p[i].x == a.x && p[i].y == a.y)continue;
        if(p[i].x == b.x && p[i].y == b.y)continue;
        if(p[i].x > max(a.x, b.x) || p[i].x < min(a.x, b.x))continue;
        if(p[i].y > max(a.y, b.y) || p[i].y < min(a.y, b.y))continue;
        if((p[i] - a) * (b - p[i]) == 0)return 1;
    }
    return 0;
}
bool check()
{
    if(top <= 2)return 0;
    for(int i = 1; i < top; i++)
        if(!checkline(q[i], q[i + 1]))
            return 0;
    if(!checkline(q[top], q[1]))
        return 0;
    return 1;
}
int main()
{
    int T = read();
    while(T--)
    {
        n = read();
        for(int i = 1; i <= n; i++)
            p[i].x = read(), p[i].y = read();
        if(n < 6)
        {
            puts("NO");
            continue;
        }
        graham();
        if(check())puts("YES");
        else puts("NO");
    }
    return 0;
}

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, top;

struct P{

double x, y;

friend P operator-(P a, P b){

return (P){a.x - b.x, a.y - b.y};

}

friend int operator*(P a, P b){

return a.x * b.y - a.y * b.x;

}

friend bool operator<(P a, P b){

if(a.y == b.y)return a.x < b.x;

return a.y < b.y;

}

friend int dis2(P a){

return a.x * a.x + a.y * a.y;

}

}p[1005], q[1005];

bool cmp(P a, P b)

{

if((a - p[1]) * (b - p[1]) == 0)

return dis2(a - p[1]) < dis2(b - p[1]);

return (a - p[1]) * (b - p[1]) > 0;

}

void graham()

{

top = 0;

for(int i = 1; i <= n; i++)

if(p[i] < p[1])swap(p[i], p[1]);

sort(p + 2, p + n + 1, cmp);

for(int i = 1; i <= n; i++)

{

while(top > 1 && (q[top] - q[top - 1]) * (p[i] - q[top - 1]) <= 0)

top--;

q[++top] = p[i];

}

bool checkline(P a, P b)

{

for(int i = 1; i <= n; i++)

{

if(p[i].x == a.x && p[i].y == a.y)continue;

if(p[i].x == b.x && p[i].y == b.y)continue;

if(p[i].x > max(a.x, b.x) || p[i].x < min(a.x, b.x))continue;

if(p[i].y > max(a.y, b.y) || p[i].y < min(a.y, b.y))continue;

if((p[i] - a) * (b - p[i]) == 0)return 1;

}

return 0;

}

bool check()

{

if(top <= 2)return 0;

for(int i = 1; i < top; i++)

if(!checkline(q[i], q[i + 1]))

return 0;

if(!checkline(q[top], q[1]))

return 0;

return 1;

}

int main()

{

int T = read();

while(T--)

{

n = read();

for(int i = 1; i <= n; i++)

p[i].x = read(), p[i].y = read();

if(n < 6)

{

puts("NO");

continue;

}

graham();

if(check())puts("YES");

else puts("NO");

}

return 0;

}

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define eps 1e-13
#define LL long long
#define LB long double
#define pa pair<LB,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int pre[200005],nxt[200005];
bool del[200005];
LB ans;
struct P{
    LB x,y;
    friend LB operator*(P a,P b){
        return a.x*b.y-a.y*b.x;
    }
    friend P operator+(P a,P b){
        return (P){a.x+b.x,a.y+b.y};
    }
    friend P operator-(P a,P b){
        return (P){a.x-b.x,a.y-b.y};
    }
    friend P operator*(P a,LB b){
        return (P){a.x*b,a.y*b};
    }
    friend LB dis(P a){
        return sqrt(a.x*a.x+a.y*a.y);
    }
}p[200005];
void print(P a)
{
    printf("(%.3Lf,%.3Lf)",a.x,a.y);
}
struct L{
    P a,b;
    friend P cp(L a,L b){// crossover point
        double k1,k2,t;
		k1=(a.a-b.b)*(b.a-b.b),k2=(b.a-b.b)*(a.b-b.b);
		t=k1/(k1+k2);
		return (P){a.a.x+(a.b.x-a.a.x)*t,a.a.y+(a.b.y-a.a.y)*t};
    }
}l[200005];
L ab(P a,P b,P c){ // angle a,b,c // angular bisector
    LB l1=dis(a-b),l2=dis(b-c);
    a=b+(a-b)*(l2/l1);
    P t=a+c;t.x/=2;t.y/=2;
    return (L){b,t};        
}
LB dis(L l,P a){
    return abs((l.b-l.a)*(a-l.a))/dis(l.a-l.b);
}
priority_queue<pa,vector<pa>,greater<pa> >pq;
void add(int x)
{
    L ll=l[pre[x]],rl=l[nxt[x]];
    LB t;
    if(fabs((ll.b-ll.a)*(rl.b-rl.a))<eps)
        t=dis(ll,rl.b)/2;
    else 
    {
        L l1=ab(ll.a,ll.b,l[x].b);
        L l2=ab(l[x].a,rl.a,rl.b);
        if(fabs((l1.b-l1.a)*(l2.b-l2.a))<eps)t=1e20;
        else 
        {
            P p=cp(l1,l2);t=dis(l[x],p);
        }
    }
    pq.push(mp(t,x));
}
int main()
{
    while(1)
    {
        n = read();
        if(n == 0)break;
        ans = 0;
        for(int i=1;i<=n;i++)
            del[i] = 0;
        while(!pq.empty())
            pq.pop();
        for(int i=1;i<=n;i++)
            p[i].x=read(),p[i].y=read();
        p[n+1]=p[1];
        for(int i=1;i<=n;i++)
            l[i]=(L){p[i],p[i+1]};
        for(int i=1;i<=n;i++)
            pre[i]=i-1,nxt[i]=i+1;
        pre[1]=n;nxt[n]=1;
        for(int i=1;i<=n;i++)add(i);
        for(int i=1;i<=n-2;i++)
        {
            int id=pq.top().second;
            while(del[id])
            {
                pq.pop();
                id=pq.top().second;
            }
            int L=pre[id],R=nxt[id];del[id]=1;
            ans=max(ans,pq.top().first);
            pq.pop();
            if(abs((l[L].b-l[L].a)*(l[R].b-l[R].a))<eps)break;
            P p=cp(l[L],l[R]);
            l[L].b=l[R].a=p;
            nxt[L]=R;pre[R]=L;
            add(L);add(R);
        }
        printf("%.6lf\n",(double)ans);
    }
    return 0;
}

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

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define abs(x) ((x)>0?(x):-(x))

#define eps 1e-13

#define LL long long

#define LB long double

#define pa pair<LB,int>

#define mp(x,y) make_pair(x,y)

using namespace std;

LL read()

{

LL x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int pre[200005],nxt[200005];

bool del[200005];

LB ans;

struct P{

LB x,y;

friend LB operator*(P a,P b){

return a.x*b.y-a.y*b.x;

}

friend P operator+(P a,P b){

return (P){a.x+b.x,a.y+b.y};

}

friend P operator-(P a,P b){

return (P){a.x-b.x,a.y-b.y};

}

friend P operator*(P a,LB b){

return (P){a.x*b,a.y*b};

}

friend LB dis(P a){

return sqrt(a.x*a.x+a.y*a.y);

}

}p[200005];

void print(P a)

{

printf("(%.3Lf,%.3Lf)",a.x,a.y);

}

struct L{

P a,b;

friend P cp(L a,L b){// crossover point

double k1,k2,t;

k1=(a.a-b.b)*(b.a-b.b),k2=(b.a-b.b)*(a.b-b.b);

t=k1/(k1+k2);

return (P){a.a.x+(a.b.x-a.a.x)*t,a.a.y+(a.b.y-a.a.y)*t};

}

}l[200005];

L ab(P a,P b,P c){ // angle a,b,c // angular bisector

LB l1=dis(a-b),l2=dis(b-c);

a=b+(a-b)*(l2/l1);

P t=a+c;t.x/=2;t.y/=2;

return (L){b,t};

}

LB dis(L l,P a){

return abs((l.b-l.a)*(a-l.a))/dis(l.a-l.b);

}

priority_queue<pa,vector<pa>,greater<pa> >pq;

void add(int x)

{

L ll=l[pre[x]],rl=l[nxt[x]];

LB t;

if(fabs((ll.b-ll.a)*(rl.b-rl.a))<eps)

t=dis(ll,rl.b)/2;

else

{

L l1=ab(ll.a,ll.b,l[x].b);

L l2=ab(l[x].a,rl.a,rl.b);

if(fabs((l1.b-l1.a)*(l2.b-l2.a))<eps)t=1e20;

else

{

P p=cp(l1,l2);t=dis(l[x],p);

}

pq.push(mp(t,x));

}

int main()

{

while(1)

{

n = read();

if(n == 0)break;

ans = 0;

for(int i=1;i<=n;i++)

del[i] = 0;

while(!pq.empty())

pq.pop();

for(int i=1;i<=n;i++)

p[i].x=read(),p[i].y=read();

p[n+1]=p[1];

for(int i=1;i<=n;i++)

l[i]=(L){p[i],p[i+1]};

for(int i=1;i<=n;i++)

pre[i]=i-1,nxt[i]=i+1;

pre[1]=n;nxt[n]=1;

for(int i=1;i<=n;i++)add(i);

for(int i=1;i<=n-2;i++)

{

int id=pq.top().second;

while(del[id])

{

pq.pop();

id=pq.top().second;

}

int L=pre[id],R=nxt[id];del[id]=1;

ans=max(ans,pq.top().first);

pq.pop();

if(abs((l[L].b-l[L].a)*(l[R].b-l[R].a))<eps)break;

P p=cp(l[L],l[R]);

l[L].b=l[R].a=p;

nxt[L]=R;pre[R]=L;

add(L);add(R);

}

printf("%.6lf\n",(double)ans);

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论