題目大意:維護一個平面,支持三種操作:
0.加入一條直線(給的是兩點式)
1.刪除一條直線
2.詢問到所有直線距離平方和最小的點
題解見 www.2cto.com
我只是貼代碼供參考的- -
注意我的abcdef和題解設的不一樣- -
這簡單題WA了兩頁- -
#include#include #include #include #include #define M 120100 #define EPS 1e-7 using namespace std; struct Line{ double A,B,C; Line() {} Line(double x1,double y1,double x2,double y2) { A=y1-y2; B=x2-x1; C=x1*y2-x2*y1; } }lines[M]; int n,tot; double a,b,c,d,e,f; //ans=a*x^2+b*y^2+c+d*x*y+e*x+f*y int main() { int i,p,x; double x1,y1,x2,y2; double A,B,C,temp; cin>>n; for(i=1;i<=n;i++) { scanf(%d,&p); switch(p) { case 0: scanf(%lf%lf%lf%lf,&x1,&y1,&x2,&y2); lines[++tot]=Line(x1,y1,x2,y2); A=lines[tot].A; B=lines[tot].B; C=lines[tot].C; temp=A*A+B*B; a+=A*A/temp; b+=B*B/temp; c+=C*C/temp; d+=2*A*B/temp; e+=2*A*C/temp; f+=2*B*C/temp; break; case 1: scanf(%d,&x); A=lines[x].A; B=lines[x].B; C=lines[x].C; temp=A*A+B*B; a-=A*A/temp; b-=B*B/temp; c-=C*C/temp; d-=2*A*B/temp; e-=2*A*C/temp; f-=2*B*C/temp; break; case 2: if(fabs(d*d-4*a*b) EPS||fabs(d)>EPS) A=2*a,B=d,C=e; else if(fabs(b)>EPS||fabs(d)>EPS) A=d,B=2*b,C=f; else { printf(%.2lf ,0.0); break; //這裡我不明白為什麼 望高人指點 } if(fabs(B)