UVa 1643 – Angle and Squares [几何]

```#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;
inline int dcmp(double x) {
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct Point{
double x, y;
Point():x(0), y(0){}
Point(double x, double y):x(x), y(y){}
Point(const Point & rhs):x(rhs.x), y(rhs.y){}
Point operator + (Point rhs) const { return Point(x+rhs.x, y+rhs.y); }
Point operator - (Point rhs) const { return Point(x-rhs.x, y-rhs.y); }
Point operator * (double t) const { return Point(x*t, y*t); }
bool operator < (const Point & rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
bool operator == (const Point & rhs) const {
return !dcmp(x-rhs.x) && !dcmp(y-rhs.y);
}
double dot(Point rhs) { return x * rhs.x + y * rhs.y; }
double cross(Point rhs) { return x * rhs.y - y * rhs.x; }
double length() { return hypot(x, y); }
double angle(Point rhs) { return acos(dot(rhs)/length()/rhs.length()); }
}
};
typedef Point Vec;
typedef deque<Vec> Polygon;

double triArea(Point a, Point b, Point c) {
return (b-a).cross(c-a)/2.0;
}
double cross(Vec lhs, Vec rhs) { return lhs.cross(rhs); }
double dot(Vec lhs, Vec rhs) { return lhs.dot(rhs); }

Point getLineInter(Point p, Vec v, Point q, Vec w) {
Vec u = p - q;
double t = cross(w, u) / cross(v, w);
return p + v * t;
}
bool inSeg(Point p, Point a1, Point a2) {
return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
bool onSeg(Point p, Point a1, Point a2) {
return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) <= 0;
}
bool segProperInter(Point a1, Point a2, Point b1, Point b2) {
double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
return dcmp(c1 * c2) < 0 && dcmp(c3 * c4) < 0;
}
bool segInter(Point a1, Point a2, Point b1, Point b2) {
double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
return dcmp(c1 * c2) <= 0 && dcmp(c3 * c4) <= 0;
}

double polygonArea(const Polygon & p) {
double area = 0;
int sz = p.size();
for (int i = 2; i < sz; ++i)
area += triArea(p[0], p[i - 1], p[i]);
return area / 2;
}
bool isProtrude(const Polygon & p) {
Polygon v;
int sz = p.size();
for (int i = 0; i < sz; ++i)
v.push_back(p[(i + 1) % sz] - p[i]);
int flag = dcmp(cross(v[1], v[0]));
for (int i = 0; i < sz; ++i)
if (dcmp(cross(v[(i + 1) % sz], v[i])) != flag)
return false;
return true;
}
Polygon convexHull(Polygon p){
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int i, n = p.size(), m = 0;
Polygon ch(n + 1);
for(i = 0; i < n; ++i){
while(m >= 2 && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
ch[m++] = p[i];
}
int k = m;
for(i = n - 2; i >= 0; --i){
while(m > k && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
ch[m++] = p[i];
}
if(n > 1) --m; ch.resize(m);
return ch;
}

//----------------------------------------------------------------------------------

int n;

int main() {
ios::sync_with_stdio(false);
while(cin >> n, n) {
Vec a, b; cin >> a.x >> a.y >> b.x >> b.y;
double len = 0, area = 0;
for(int i = 0; i < n; ++i) {
double x; cin >> x;
len += x;
area += x * x / 2;
}
double k1 = a.y / a.x, k2 = b.y / b.x;
if(k1 > k2) swap(k1, k2);
double x1 = len*(k2+1)/(k2-k1), y1 = k1*x1;
double x2 = len*(k1+1)/(k2-k1), y2 = k2*x2;
area = triArea(Point(0, 0), Point(x1, y1), Point(x2, y2)) - area;
// area = Vec(x1, y1).cross(Vec(x2, y2)) / 2 - area;
cout << fixed << setprecision(3) << area << endl;
}
return 0;
}
```