OpenJudge/1054.cpp at master · tongtzeho/OpenJudge · GitHub

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
#include<iostream>
#include<stdlib.h>
using namespace std;
struct pointorder
{
	short x,y;
}*p;
short **b;
inline short maxnum(short,short);
inline short minnum(short,short);
short calc(short,short,short,short,short,short);
inline bool notin(short,short,short,short);
inline short maxnum(short x,short y)
{
	if(x>y)return x;
	return y;
}
inline short minnum(short x,short y)
{
	if(x<y)return x;
	return y;
}
short calc(short x1,short y1,short x2,short y2,short r,short c)
{
	short dx=x2-x1,dy=y2-y1;
	if(dx==0)return (c-y1)/dy+1;
	if(dy==0)return (r-x1)/dx+1;
	if(dy>0)return minnum((r-x1)/dx+1,(c-y1)/dy+1);
	short temp;
	dy=-dy;
	if(y1%dy==0)temp=y1/dy;
	else temp=y1/dy+1;
	return minnum((r-x1)/dx+1,temp);
}
inline bool notin(short x,short y,short r,short c)
{
	if(x<=0||y<=0||x>r||y>c)return 1;
	return 0;
}
int cmp(const void *p1,const void *p2)
{
	struct pointorder *p3=(pointorder*)p1;
	struct pointorder *p4=(pointorder*)p2;
	if(p3->x!=p4->x)return p3->x-p4->x;
	return p3->y-p4->y;
}
int main()
{
	int i,j;
	short r,c,x,y,dx,dy,maxtotal,total,n,best=0;
	bool t;
	cin>>r>>c>>n;
	b=new short*[r+1];
	for(i=0;i<=r;i++)
	{
		b[i]=new short[c+1];
		for(j=0;j<=c;j++)
			b[i][j]=-1;
	}
	p=new pointorder[n+1];
	for(i=1;i<=n;i++)
	{
		cin>>x>>y;
		p[i].x=x;
		p[i].y=y;
		b[x][y]=0;
	}
	maxtotal=maxnum(r,c);
	if(maxtotal<3)
	{
		cout<<0;
		return 0;
	}
	p[0].x=p[0].y=0;
	qsort(p,n+1,sizeof(p[0]),cmp);
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			if(2*p[i].x<=p[j].x||2*p[i].y<=p[j].y||p[j].y+c<=2*p[i].y)
			{
				total=calc(p[i].x,p[i].y,p[j].x,p[j].y,r,c);
				x=p[j].x;
				y=p[j].y;
				if(b[x][y]<total)
				{
					dx=p[j].x-p[i].x;
					dy=p[j].y-p[i].y;
				    do
					{
					    x+=dx;
					    y+=dy;
					    if(notin(x,y,r,c))
						{
						    t=1;
						    break;
						}
					    else if(b[x][y]==-1||b[x][y]>=total)
						{
						    t=0;
						    break;
						}
					}while(1);
				    if(t)
					{
					    best=maxnum(best,total);
					    if(best==maxtotal)
						{
						    cout<<best;
						    return 0;
						}
					    x-=dx;
					    y-=dy;
					    do
						{
						    b[x][y]=best;
						    x-=dx;
						    y-=dy;
						}while(!notin(x,y,r,c));
					}
				}
			}
		}
	if(best<3)cout<<0;
	else cout<<best;
	return 0;
}