矩形面积
Time Limit: 20 Sec Memory Limit: 256 MB
题目连接
http://acdream.info/problem?pid=1754
Description
Input
第一行一个正整数 T，代表测试数据组数(1≤T≤20)，接下来 T 组测试数据。
每组测试数据占若干行，第一行一个正整数 N(1≤N<≤1000)，代表矩形的数量。接下来 N 行，每行 8 个整数x1,y1,x2,y2,x3,y3,x4,y4，代表矩形的四个点坐标，坐标绝对值不会超过10000。
Output
对于每组测试数据，输出两行：
第一行输出"Case #i:"，i 代表第 i 组测试数据。 第二行包含1 个数字，代表面积最小的矩形的面积，结果保留到整数位。
Sample Input
2 2 5 10 5 8 3 10 3 8 8 8 8 6 7 8 7 6 1 0 0 2 2 2 0 0 2
Sample Output
Case #1: 17 Case #2: 4
HINT
题意
题解：
套版，套版
代码：
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 10007 #define eps 1e-9 int Num; char CH[20]; const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void P(int x) { Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts(""); } //************************************************************************************** struct Point { double x,y; Point(){} Point(double x0,double y0):x(x0),y(y0){} }; const int INF = 999999999; Point p[maxn]; int con[maxn]; int cn; int n; struct Line { Point a,b; Line(){} Line(Point a0,Point b0):a(a0),b(b0){} }; double xm(Point o,Point a,Point b) { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); } double dm(Point o,Point a,Point b) { return (a.x-o.x)*(b.x-o.x)+(a.y-o.y)*(b.y-o.y); } int sgn(double a) { return a<-eps?-1:a>eps; } double dist(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int cmp(Point a,Point b) { double d=xm(p[0],a,b); if(d>0) return 1; if(d==0 && dist(p[0],a)<dist(p[0],b)) return 1; return 0; } void Graham() { int i,ind=0; for(i=1;i<n;i++) if(p[ind].y>p[i].y || (p[ind].y==p[i].y) && p[ind].x>p[i].x) ind=i; swap(p[ind],p[0]); sort(p+1,p+n,cmp); con[0]=0; con[1]=1; cn=1; for(i=2;i<n;i++) { while(cn>0 && sgn(xm(p[con[cn-1]],p[con[cn]],p[i]))<=0) cn--; con[++cn]=i; } int tmp=cn; for(i=n-2;i>=0;i--) { while(cn>tmp && sgn(xm(p[con[cn-1]],p[con[cn]],p[i]))<=0) cn--; con[++cn]=i; } } double Solve() { int t,r,l; double ans=INF; t=r=1; if(cn<3) return 0; for(int i=0;i<cn;i++) { while(sgn(xm(p[con[i]],p[con[i+1]],p[con[t+1]])-xm(p[con[i]],p[con[i+1]],p[con[t]]))>0) t=(t+1)%cn; while(sgn(dm(p[con[i]],p[con[i+1]],p[con[r+1]])-dm(p[con[i]],p[con[i+1]],p[con[r]]))>0) r=(r+1)%cn; if(!i) l=r; while(sgn(dm(p[con[i]],p[con[i+1]],p[con[l+1]])-dm(p[con[i]],p[con[i+1]],p[con[l]]))<=0) l=(l+1)%cn; double d=dist(p[con[i]],p[con[i+1]]); double tmp=xm(p[con[i]],p[con[i+1]],p[con[t]])*(dm(p[con[i]],p[con[i+1]],p[con[r]])-dm(p[con[i]],p[con[i+1]],p[con[l]]))/d/d; ans=min(ans,tmp); } return ans; } int main() { int i; int T, cas = 0; scanf("%d", &T); while(T--) { scanf("%d", &n); n *= 4; for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); Graham(); printf("Case #%d: %.0f ",++cas, Solve()); } return 0; }