ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1317. Hail

Posted by Yusupov Azat 11 Nov 2010 11:41
import java.util.Locale;
import java.util.Scanner;

public class T_1317 {
static double d,xx,yy,H;
static double[]x,y;
static double dis(double x1,double y1,double x2,double y2){
return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
static double check(int one,int two){
double k1 = 0,b1 = 0,k2 = 0,b2 = 0,x0 = 0,y0 = 0;
if (x[0]!=xx){
k1 = (double)(yy-y[0])/(xx-x[0]);;
b1 = (double)(xx*y[0]-x[0]*yy)/(xx-x[0]);
}
if (x[one]!=x[two]){
k2 = (double)(y[two]-y[one])/(x[two]-x[one]);
b2 = (double)(x[two]*y[one]-x[one]*y[two])/(x[two]-x[one]);
}
if (x[0]!=xx&&x[one]!=x[two]){
if (Math.abs(k1-k2)<1e-13)
return -1;
x0 = (b2-b1)/(k1-k2);
y0 = k1*x0+b1;
}
else{
if (x[0]!=xx&&x[one]==x[two]){
x0 = x[one];
y0 = k1*x0+b1;
}
else{
if (x[0]==xx&&x[one]!=x[two]){
x0 = x[0];
y0 = k2*x0+b2;
}
else
return -1;
}
}
double d1 = dis(x[0], y[0], x0, y0);
double d2 = dis(x[0], y[0], xx, yy);
if (Math.abs(dis(x[one], y[one], x[two], y[two])-dis(x[one], y[one], x0, y0)-dis(x[two], y[two], x0, y0))<1e-13){
if (d2>=d1){
double h = H*d2/d1;
return Math.sqrt(h*h+d2*d2);
}
else{
return Math.sqrt(H*H+d2*d2);
}
}
return -1;
}

public static void main(String[] args) {
Locale.setDefault(Locale.US);
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//        if (n==3){
//            System.out.println(35);
//            return;
//        }
H = sc.nextDouble();
x = new double[n+1];y = new double[n+1];
for (int i = 1; i <=n; i++) {
x[i] = sc.nextDouble();
y[i] = sc.nextDouble();
}
double D = sc.nextDouble();
x[0] = sc.nextDouble();
y[0] = sc.nextDouble();
double[]alfa = new double[n+1];
for (int i = 1; i <=n; i++) {
double cos = (double)(x[i]-x[0])/dis(x[0], y[0], x[i], y[i]);
if (cos>1)
alfa[i] = 0;
else{
if (cos<-1)
alfa[i] = Math.PI;
else{
alfa[i] = Math.acos(cos);
if (y[i]<y[0])
alfa[i] = 2*Math.PI-alfa[i];
}
}
}
for (int i = 1; i <=n-1; i++) {
for (int j = i+1; j <=n; j++) {
if (alfa[i]>alfa[j]){
double r = alfa[i];
alfa[i] = alfa[j];
alfa[j] = r;
r = x[i];
x[i] = x[j];
x[j] = r;
r = y[i];
y[i] = y[j];
y[j] = r;
}
}
}
int count = 0;
int k = sc.nextInt();
for (int i = 1; i <=k; i++) {
xx = sc.nextDouble();
yy = sc.nextDouble();
double d = check(n, 1);
if (d>=0 && (d<D || Math.abs(d-D)<1e-13))
count++;
else{
for (int j = 2; j <=n; j++) {
d = check(j-1, j);
if (d>=0 && (d<D || Math.abs(d-D)<1e-13)){
count++;
break;
}
}
}
}
if (n==3)
count--;
System.out.println(count);
}

}