Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对这个判定条件有疑问 附AC代码

Posted by ThirdLiu at 2016-07-19 11:33:48 on Problem 1054
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;


typedef struct{
	int x, y;
}Cord;

Cord map_t[5002];
int col, row;

int compare_a(const void* a, const void* b)  
{                   //按照行号排序,行号相等时按列号升序排序  
    Cord *p, *q;  
    p = (Cord*)a;  
    q = (Cord*)b;  
    if (p->x == q->x) return (p->y - q->y);  
    else   return (p->x - q->x);  
}  

int binary_search(Cord next, int begin, int end){
	
	if(begin > end)
		return -1;
	int mid = (begin + end) / 2;
	Cord tmp = map_t[mid];
	if(compare(&tmp, &next) < 0)
		return binary_search(next, mid + 1, end);
	else if(compare(&tmp, &next) > 0)
		return binary_search(next, begin, mid - 1);
	else 
		return mid;
	return -1;
}



int find_path(Cord st, int dx, int dy, int begin, int size){

	int step = 2;
	int inx = begin;	
	Cord tmp;
	tmp.x = st.x + dx;
	tmp.y = st.y + dy;
	while (tmp.x>=1 && tmp.x<=col && tmp.y>=1 & tmp.y<=row) { // 为什么一定要判断x大于等于1 不是题目有限定吗 一定会在1开始的
		if(binary_search(tmp, 1, size) < 0)
			return 0;
		tmp.x += dx;
		tmp.y += dy;
		++step;
	}
	return step;
	
}



int main(){

	int n = 0;
	int i = 1;
	scanf("%d %d", &col, &row);
	cin>>n;
	for(int i = 1; i <= n; ++i){
		scanf("%d %d", &(map_t[i].x), &(map_t[i].y));
	}
	qsort(map_t + 1, n, sizeof(Cord), compare);
	int max_step = 2;
	for(int i = 1; i <= n - 1; ++i){
		for(int j = i + 1; j <= n; ++j){
			int dx, dy;
			dx = map_t[j].x - map_t[i].x;
			dy = map_t[j].y - map_t[i].y;
			if(map_t[i].x - dx >= 1 && map_t[i].y - dy >= 1
					&& map_t[i].x - dx <= col && map_t[i].y - dy <= row)
				continue;
			if(map_t[j].x + (max_step - 1) * dx > col) 
				break;
			int y0 = map_t[i].y + max_step * dy;
			//if (y0 > row || y0 < 1) continue;
			int tmp = find_path(map_t[j], dx, dy, j, n);
			if(tmp > max_step)
				max_step = tmp;
		}
	}
	if(max_step == 2)
		max_step = 0;
	cout<<max_step<<endl;	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator