0 0 0 0

area Time limit: 2000/1000 ms ( java/others ) memory limit: 32768/32768 k ( java/others )
Total submission ( s ): 930 accepted submission ( s ): 368

The problem description was recently used by air force to participate in a real battle acquisition. The content of the drill is an island. ..
As an excellent pilot, the task is to complete, of course, with a good operation, to smooth the bomb to a location in the island, but mr. is more concerned?
Island is an irregular polygon, and the explosive radius of the bomb is R.
only knows that the of the island in ( x, y, h ) is at the level of velocity at which the velocity of the island is destroyed, and the size of the

Input first entered three numbers representing the coordinates of the ( x, y, h );
Then enter two numbers to represent the current speed ( x1, deduction ) of the airplane.
Then enter the explosion radius R of the bomb.
Enter a number n, which represents the island from n points;
Finally, enter n lines, enter one ( x ', y ') coordinates, representing the vertices of the island ( or ). ( 3 <= n <100000 )

Output output a two decimal, representing the area of the island that's actually fired.
Sample Input
0 0 2000
100 0
1900 100
2000 100
2000 -100
1900 -100

Sample Output

Source 2009 multi-university training contest 10 - host by nit
A recommend gaojie | we've carefully selected several similar problems for you: 2891 2893 2895 2896
It's a lot of reference to the blog drawing. click on the link.

Here's the template program, and 110 rows. Some template 300 +, 400 + on the web. True.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-12;
const int maxn = 1e5+5;
double X0,Y0,h,R;
int n;
struct node{
 double x,y;
 node(double xx, double yy){ x = xx; y = yy; }
 node operator -(node s){ return node(x-s.x,y-s.y); }
 node operator +(node s){ return node(x+s.x,y+s.y); }
 double operator *(node s){ return x*s.x+y*s.y; }
 double operator ^(node s){ return x*s.y-y*s.x; }
double max(double a, double b){return a>b?a:b;}
double min(double a, double b){return a<b?a:b;}
double len(node a){return sqrt(a*a);}
double dis(node a, node b){return len(b-a);}//任意两点间的距离
double cross(node a, node b, node c){return (b-a)^(c-a);}//叉乘
double dot(node a, node b, node c){return (b-a)*(c-a);}//点乘
bool judge(node a, node b, node c){
//判断 c是否在线段ab上(前提是c在直线ab上)
 if (c.x>=min(a.x,b.x)
 && c.x<=max(a.x,b.x)
 && c.y>=min(a.y,b.y)
 && c.y<=max(a.y,b.y))
 return 1;
 return 0;
double area(node b, node c, double r){
 node a(0.0,0.0);
 if (dis(b,c)<eps) return 0.0;
 double h = fabs(cross(a,b,c))/dis(b,c);
 if (dis(a,b)>r-eps && dis(a,c)>r-eps) {
 double angle = acos(dot(a,b,c)/dis(a,b)/dis(a,c));//点乘公式推导的
 if (h>r-eps) {return 0.5*r*r*angle;}//直接求扇形面积
 else if (dot(b,a,c)>0 && dot(c,a,b)>0) {
 double angle1 = 2*acos(h/r);
 return 0.5*r*r*fabs(angle-angle1) + 0.5*r*r*sin(angle1);
 else return 0.5*r*r*angle;
 else if (dis(a,b)<r+eps && dis(a,c)<r+eps) {return 0.5*fabs(cross(a,b,c));}//两个端点在圆内
 else {
 if (dis(a,b)>dis(a,c)) swap(b,c);//假设b点更接近圆心
 if (fabs(dis(a,b))<eps) {return 0.0;}
 if (dot(b,a,c)<eps) {
 double angle1 = acos(h/dis(a,b));
 double angle2 = acos(h/r) - angle1;
 double angle3 = acos(h/dis(a,c)) - acos(h/r);
 return 0.5*dis(a,b)*r*sin(angle2) + 0.5*r*r*angle3;
 else {
 double angle1 = acos(h/dis(a,b));
 double angle2 = acos(h/r);
 double angle3 = acos(h/dis(a,c)) - angle2;
 return 0.5*r*dis(a,b)*sin(angle1+angle2) + 0.5*r*r*angle3;
void init(){
 double x1,y1;
 scanf("%lf %lf",&x1,&y1);
 for (int i=0; i<n; i++) scanf("%lf %lf",&point[i].x,&point[i].y);
 double t = sqrt(2*h*1.0/10);
 X0 += x1*t;
 Y0 += y1*t;
 point[n] = point[0];
int main(){
 while (scanf("%lf %lf %lf",&X0,&Y0,&h)!=EOF){
 node O(X0,Y0);
 for (int i=0; i<=n; i++) point[i] = point[i]-O;
 O = node(0.0,0.0);
 double sum = 0,s;
 for (int i=0; i<n; i++) {
 s = area(point[i],point[i+1],R);
 if (cross(O,point[i],point[i+1])>0) sum +=s;
 else sum -= s;
 return 0;

Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs