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

大水,对精度没什么要求貌似,正常写就能过

Posted by KatrineYang at 2016-09-03 04:27:24 on Problem 1263
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int n;

int main() {
	int cnt = 0;
	while(1){
		scanf("%d", &n);
		if(n==0) break;
		cnt++;
		printf("Scene %d\n", cnt);
		int x[30], y[30], r[30];
		for(int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &r[i]);
		int x0_, y0_, dx_, dy_;
		scanf("%d%d%d%d", &x0_, &y0_, &dx_, &dy_);
		double x0 = x0_, y0 = y0_, dx = dx_, dy = dy_;
		double norm = sqrt(dx*dx + dy*dy);
		dx /= norm, dy /= norm;
		int hit = 0;
		while(hit <= 10){
			double tmin = 1000000000.0;
			int arg = -1;
			for(int i = 1; i <= n; i++){
				double b = dx * (x0-x[i]) + dy * (y0-y[i]);
				double a = dx*dx+dy*dy;
				double c = (x0-x[i])*(x0-x[i]) + (y0-y[i])*(y0-y[i]) - r[i]*r[i];
				double delta = b*b - a*c;
				double t;
				if(delta >= 0){
					t = (-b-sqrt(delta))/a;
				}
				if(delta >= 0 && t >= 0){
					if(t < tmin){
						tmin = t;
						arg = i;
					}
				}
			}
			if(arg == -1){
				printf("inf\n");
				break;
			}
			else if(hit == 10){
				printf("...\n");
				break;
			}
			hit++;
			printf("%d ", arg);
			double x_ = x0+tmin*dx, y_ = y0+tmin*dy;
			x0 = x_, y0 = y_;
			double tx = x_ - x[arg], ty = y_ - y[arg];
			double tempDx = (ty*ty-tx*tx)*dx-2*tx*ty*dy, tempDy = dy*(tx*tx-ty*ty)-2*dx*tx*ty;
			double norm = sqrt(tempDx*tempDx + tempDy*tempDy);
			dx = tempDx/norm, dy = tempDy/norm;
		}
		printf("\n");
	}
	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